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. Practice
  2. Data Structures
  3. Arrays
  4. Array Manipulation
  5. Discussions

Array Manipulation

  • tomade + 3 comments

    Yes, that makes more sense and saves on memory and running time. Using a defaultdict in Python:

    from collections import defaultdict

sums = defaultdict(int)
_, n_ranges = (int(x) for x in input().split())

for _ in range(n_ranges):
    start, stop, value = (int(x) for x in input().split())
    sums[start] += value
    sums[stop+1] -= value

max_val = running_val = 0
for _, val in sorted(sums.items()):
    running_val += val
    max_val = max(max_val, running_val)

print(max_val)
    • Chainly + 0 comments

      it is great that we don't have to store every key.

    • rajasanwir_iitk1 + 2 comments
      n, m = input().strip().split(' ')
n, m = [int(n), int(m)]
l = [0] * (n+1)
for a0 in range(m):
    a, b, k = input().strip().split(' ')
    a, b, k = [int(a), int(b), int(k)]
    l[a:b+1] = list(map(lambda x:x+k,l[a:b+1]))
print(max(l))

      The above code is showing runtime error for test case 7 onwards. please suggest the reason?

      • david_barkhuizen + 2 comments

        I experience the same issue. If I run test case 13 locally, my code passes, but if I try the same code remotely on HR, cases 7 -> 13 all fail. Out of memory ?

        • mercy1 + 1 comment
          [deleted]
          • haritzrahman98 + 0 comments

            why deleted :(

        • Kanahaiya + 1 comment

          Hi,

          Most of the peope solved this problem but time complexity of solution is O(n*m) (due to two nested for loops)which can not be used to solve this problem for given time constraint, so you need better approach which beats O(n*m)

          I have created a video tutorial for you and uploaded the same on youtube with complete explanation along with code complexity analysis.

          Here is the video tutorial for my solution O(n+m) complexity passed all test cases.

          https://youtu.be/hDhf04AJIRs

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

          • rishirajsharma + 0 comments
            // Complete the arrayManipulation function below.
static long arrayManipulation(int n, int[][] queries , int jj) {

    long[] a = new long[n+1];
    long max=0;
    int i=0;
    int start = queries[i][0];
    int end = queries[i][1];
    int sum = queries[i][2];
    while(i<jj){
        // System.out.println(jj+"=jj"+i);
        System.out.println("s"+start+"e"+end+"sum"+sum+"i"+i);
        if(start<=end){
            a[start]=a[start]+sum;
            if(a[start]>max){
                max=a[start];
            }
            System.out.println("start"+start);
            start++;
        }else{
            i++;
            if(i<jj){
            System.out.println("i"+i);
            start = queries[i][0];
            end = queries[i][1];
            sum = queries[i][2];
            }
        }
        // for(int l=1;l<a.length;l++){
        //   System.out.print(a[l]+"\t");

                    Complexity is only O(n) here , right
        // }
        // System.out.println("");
    }
    return max;
}
      • pulkitpahwa + 0 comments

        I too tried the same approach. Yes, It's giving runtime error.

    • srodrig0209 + 0 comments

      Brilliant. It seems like the runtime error has since been fixed.