Ad

Hackerrank Solution In C For "Array Manipulation"

- 1 answer

long arrayManipulation(int n, int queries_rows, int queries_columns, int** queries)
{
    long num, a, b, maxnum = INT_MIN;
    long* arrptr = calloc(n, sizeof(long));
    for(int i = 0;i<(queries_rows);i++)
    {
      num = queries[i][2];
      if(num==0)
      {
          continue;
      }
      printf("%ld ", num);
      a = queries[i][0];
      b = queries[i][1];
      for(long i = a-1;i<b;i++)
      {
        arrptr[i] += num;
        if(maxnum<(arrptr[i]))
        {
            maxnum = arrptr[i];
        }
      }
  }
  free(arrptr);
  return maxnum;
}

I have to optimize this program so that it can be executed in less time can you help??

this program is supposed to initialize an array of a size n(function argument) with 0(lets call array arr) then there will be query in form
a b k
1 2 3
4 5 6

and then in array arr we have add k between the limits a and b and then return max of arr

example Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

Explanation

After the first update list will be 100 100 0 0 0.
After the second update list will be 100 200 100 100 100.
After the third update list will be 100 200 200 200 100.
The returned answer will be 200.

Ad

Answer

Since I have been working on it I found a good and understandable code on it with O(n) approach, it works well under required time and it doesn't have errors.

long arrayManipulation(int n, int queries_rows, int queries_columns, int** queries) 
{
  long num, a, b, maxnum = INT_MIN;
  int* arrptr = calloc(n, sizeof(long));
  for(int i=0;i<queries_rows;i++)
  {
   arrptr[queries[i][0] -1] +=queries[i][2];
   arrptr[queries[i][1]] -= queries[i][2];
  }
   long count = 0; 
  for(int i=0;i<n;i++)
  {
   count += arrptr[i];
   arrptr[i]=count;
      if(count>maxnum) maxnum=count;
  }
       printf("%ld\n",maxnum);
  free(arrptr);
  return maxnum;
}
Ad
source: stackoverflow.com
Ad