[Solved] Convert nested ‘for’ loop to single ‘for’ loop in java [closed]

Question

I don’t think you can avoid two loops, but you can make it sequential, instead of nested.

long[] delta = new long[ar];
for(i=0;i<k;i++)
{
    l=sc.nextLong();
    r=sc.nextLong();
    v=sc.nextLong();

    if (l-1 < r) {
        m=(int)(l-1);
        delta[m] = v;

        m=(int)r;
        if (m < delta.length) {
          delta[m] = -v;
        }
    }
}

long cumulative = 0;
for (int a = 0; a < ar.length; ++a) {
  cumulative += delta[a];
  ar[a] += cumulative;
}

Rather than keeping on incrementing the values in delta for each of the l,r ranges, this just stores a “delta” array: this stores a +v at the index where you’d start incrementing the array by v; and -v at the index where you’d stop. So, recording that the range between l and r should be incremented by v is now an O(1) operation, rather than an O(r-l) operation.

So, some portion of this array looks like:

     2    
 0 0   0 0 0 0 0   0 0 0
                -2

(I’m just vertically shifting the 2s to make it clearer)

If you calculate the cumulative sum of these elements:

     2 2 2 2 2 2  
 0 0             0 0 0 0

In other words, you can show a range where you are going to increment by 2 by storing just the start and end positions of this range.

This is what the cumulative variable stores: it’s just the sum of all the elements in the delta array to the left of and including the current position. And that’s the amount to increment the corresponding element of ar by.

Accepted Answer