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());
	}

}

You are given a list of size N, initialized with zeroes. You have to perform M operations on the list and output the maximum of final values of all the N elements in the list. For every operation, you are given three integers a, b and k. The value k needs to be added to all the elements ranging from index a through b (both inclusive).

Input Format

The first line will contain two integers N and M separated by a single space.
The next M lines will each contain three integers a, b and k separated spaces.
The numbers in the list are numbered from 1 to N.

Output Format

A single integer on a separate line line containing maximum value in the updated list.

Constraints

3 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9
Sample input:

5 3
1 2 100
2 5 100
3 4 100
Sample output:

200
Explanation

After first update list will be 100 100 0 0 0.

After second update list will be 100 200 100 100 100.

After third update list will be 100 200 200 200 100.

So the required answer will be 200.

Not an optimized one. I tried this. Only half of the test cases are passed. Also tried using Map but that also passes half of the test cases

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.