List Max. Hackerrank question for one of the companies.

ListMax.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/*
 * HACKERRANK INTERVIEW QUESTION
 * 
 * You are given a list of size N, initialized with zeroes. You have to perform M queries on the list and output the
 * maximum of final values of all the N elements in the list. For every query, you are given three integers a, b and k and
 * you have to add value k to all the elements ranging from index a to b(both inclusive).
 * 
 * Input Format
 * First line will contain two integers N and M separated by a single space.
 * Next M lines will contain three integers a, b and k separated by a single space.
 * Numbers in list are numbered from 1 to N.
 * 
 * Output Format
 * A single line containing maximum value in the final list.
 */

public class ListMax 
{
	private List<Integer> list;
	int n;
	
	public ListMax(int n)
	{
		this.n = n;
		this.list = new ArrayList<Integer>(this.n);
		//Initialize to default value of 0 for all n positions
		for(int i = 0; i < n; i++)
		{
			this.list.add(0);
		}
	}
	
	public void doOperation(int a, int b, int k)
	{
		for(int i = a-1; i < b; i++)
		{
			int val = this.list.get(i);
			val += k;
			this.list.set(i, val);
		}
	}
	
	public int listMax()
	{
		Collections.sort(this.list);
		int size = this.list.size();
		return this.list.get(size-1);
	}

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int n = Integer.parseInt(str.split(" ")[0]);
		int m = Integer.parseInt(str.split(" ")[1]);
		int opCounter = 0;
		ListMax lm = new ListMax(n);
		//If I remember it right these were the constraints for the n and m values.		
		if(n >=1 && n <= 10000000 && m >= 1 && m <= 1000000)
		{
			while(opCounter != m)
			{
				String line = sc.nextLine();
				int a = Integer.parseInt(line.split(" ")[0]);
				int b = Integer.parseInt(line.split(" ")[1]);
				int k = Integer.parseInt(line.split(" ")[2]);
				//If I remember it right these were the constraints for the a, b and k values.
				if(a >= 1 && a <= n && b >= 1 && b <= n && k >=1 && k <= 1000000000)
				{
					lm.doOperation(a, b, k);
				}
				opCounter++;
			}
		}
		System.out.println("Maximum value in the final list: " + lm.listMax());
	}

}

Any updates on this? I tried an ArrayList of long datatype which got me past 7/14 testcases. The rest timed out.

Got the same question. Petr's Fenwick tree extension can solve this -> http://petr-mitrichev.blogspot.com/2013/05/fenwick-tree-range-updates.html

The O(m * log n) solution is here -> https://gist.github.com/jakab922/ec51c6a6c56e5cab7c229d3c926ada2a
On the max settings it takes ~10-11s to execute so a rewrite in C++/Java is required to be accepted.