We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • Kanahaiya
     + 9 comments

    Hello friends,

    Brute force approach will not be sufficient to solve this problem.because time complexity of brute force algorithm is O(n * m) which is very high, for given time constraint, so you need better approach which beats O(nm).

    If interested to know why your solution did not work out.

    click here for the video explanation of generic algorithm with complexity analysis.

    or you can click on the image too to follow youtube tutorial.

    Here is the working solution with O(n+m) complexity:-

    source code :

    		static long arrayManipulation(int n, int[][] queries) {

				long outputArray[] = new long[n + 2];
				for (int i = 0; i < queries.length; i++) {
					int a = queries[i][0];
					int b = queries[i][1];
					int k = queries[i][2];
					outputArray[a] += k;
					outputArray[b+1] -= k;
				}
				long max = getMax(outputArray);
				return max;
			}

			/**
			 * @param inputArray
			 * @return
			 */
			private static long getMax(long[] inputArray) {
				long max = Long.MIN_VALUE;
				long sum = 0;
				for (int i = 0; i < inputArray.length; i++) {
					sum += inputArray[i];
					max = Math.max(max, sum);
				}
				return max;
			}

    Would really appreciate your feedback like, dislike , comment etc. on my video.

    Do not forget to upvote, if you find it useful.