4

I am doing this Array Manipulation problem from hackerrank and it tells me runtime error. From my perspective, the time complexity is O(n). But it still got this problem. Anyone could help me out?

Below is the link:

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.

For example, the length of your array of zeros . Your list of queries is as follows:

a b k
1 5 3
4 8 7
6 9 1

Add the values of between the indices and inclusive:

index -> 1 2 3  4  5 6 7 8 9 10
        [0,0,0, 0, 0,0,0,0,0, 0]
        [3,3,3, 3, 3,0,0,0,0, 0]
        [3,3,3,10,10,7,7,7,0, 0]
        [3,3,3,10,10,8,8,8,1, 0]

The largest value is after all operations are performed.

I attached my code here:

def arrayManipulation(n,queries):
    increment=[]
    value=[]
    for i in range(n):
        increment+=[0]
        value+=[0]
    for j in range(m):
        left=queries[j][0]
        right=queries[j][1]
        k=queries[j][2]
        increment[left-1]+=k
        if right>=n:
            continue
        else:
            increment[right]-=k
    value[0]=increment[0]
    for i in range(1,n):
        value[i]=value[i-1]+increment[i]
    maximum=max(value)
    return maximum

enter image description here

Improve this question
3
  • 2
    m is used before it is defined Commented Sep 16, 2018 at 19:20
  • 1
    Sorry for forgetting mentioned that m is a global variable. @yar Commented Sep 16, 2018 at 19:24
  • 1
    @Robin then provide a minimal reproducible example: complete - verifiable Commented Sep 16, 2018 at 20:51

2 Answers 2

Reset to default
10

You can simplify this problem if you just add/subtract at the correct indices - so you only have 2 ops instead of 2000 ops for

1 2000 3

Your list of queries is as follows:

a b k
1 5 3
4 8 7
6 9 1


# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[+3, 0, 0,  0, -3,  0, 0,  0, 0, 0]     # 2 index ops by 1 5 3
[+3, 0, 0, +7, -3,  0, 0, -7, 0, 0]      # 2 index ops by 4 8 7
[+3, 0, 0, +7, -3, +1, 0, -7,-1, 0]     # 2 index ops by 6 9 1

# sums:
  3  3  3  10   7   8  8   1  0  0  # for loop through list, adding all, remembering max

You get the largest value by passing through the whole list once, and simply adding up all numbers + remebering the max value while you pass through.

This simplifies the whole problem for huge lists that break your memory/computation time.

Instead of doing (for a 200k long list)

 1 2000 3  # 2000 times change value
11 2000 3  # 2000 times change value
21 2000 3  # 2000 times change value 
31 2000 3  # 2000 times change value
41 2000 3  # 2000 times change value

you do 10 value changes:

# demonstation purposes, do not create list with 200k zero entries - use a dict. see below.
[ ..., +3, ..., +3, ..., +3, ..., +3, ..., +3, ............, 
       -3, ..., -3, ..., -3, ..., -3, ..., -3, ...] 

{1:3, 11:3, 21:3, 31:3, 41:3, 2001:-3, 2011:-3, 2021:-3, 2031:-3, 2041:-3}

and when sorting by key and adding the values you get: 

 3, 6, 9, 12, 15, 18, 15, 13, 12, 9, 6, 3

You should be able to insert these things into a dict with key == position (make sure to update a key's value instead of replacing it, if it occures multiple times:

3 7 3
3 9 3
3 5 3

{3:9,7:-3, 9:-3, 5:-3} # 3 updated several times

Figuring out these ideas is what makes some hackerranks fun (plenty are just bad/unclear though).

Here is the code, have fun - it is not much of an accomplishment to copy&paste solutions - thats why I did not write the code in the first place...

maxElem, inputs = [int(n) for n in input().split(" ")]
d = {}
for _ in range(inputs):
    x, y, incr = [int(n) for n in input().split(" ")]
    d.setdefault(x,0)
    d[x]=d[x]+incr 
    if(y <= maxElem+2):
        d.setdefault(y+1,0)
        d[y+1]=d[y+1]-incr

maxx = 0
x= 0 

for i in sorted(d): 
    x+=d[i]
    if(maxx<x): 
        maxx=x

print(maxx)
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I followed this idea actually and I wrote the code above. I passed some test code and not huge data input. I need some help with the code actually @Patrick Artner
@robin Not sure how I could have given a better descripion what to do ... there you go, copy & paste it - it should work.
0

import java.io.*;

import java.math.*;

import java.security.; import java.text.;

import java.util.*;

import java.util.concurrent.*;

import java.util.regex.*;

public class Solution {

// Complete the arrayManipulation function below.
static void findMax(int n, int a[],int b[], int k[], int m)

{ int[] arr = new int[n];

// Start performing m operations
for(int i = 0; i < m; i++)
{
    // Store lower and upper index i.e. range
    int lowerbound = a[i];
    int upperbound = b[i];

    // Add 'k[i]' value at this operation to
    // whole range
    for(int j = lowerbound; j < upperbound; j++)
       arr[j]=arr[j]+k[i];
        
}

// Find maximum value after all 
// operations and return
int res = Integer.MIN_VALUE;
for(int i = 0; i < n; i++)
    res = Math.max(res, arr[i]);


    System.out.println(res);
}



public static void main(String[] args)  {
    Scanner scan = new Scanner(System.in);
    int n=scan.nextInt();
    int m=scan.nextInt();
    int a[]=new int[3];
    int b[]=new int[3];
    int k[]=new int[3];

    for(int i=0;i<a.length;i++)
    {
        a[i]=scan.nextInt();
        b[i]=scan.nextInt();
        k[i]=scan.nextInt();
    }
    findMax(n,a,b,k,m);
}

}

Improve this answer

1 Comment

Don't just dump code as an answer; add explanations. Besides that, do proper formatting.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.