HackerRank: Array Manipulation (in Data Structures)

Problem Statement

You are given a list(1-indexed) of size $n$, initialized with zeroes. You have to perform $m$ operations on the list and output the maximum of final values of all the $n$ elements in the list. For every operation, you are given three integers $a, b$ and $k$ and you have to add value to all the elements ranging from index $a$ to $b$(both inclusive).

For example, consider a list $a$ of size 3. The initial list would be $a = [0,0,0]$ and after performing the update $O(a,b,k)=(2,3,30)$ the new list would be $a = [0,30,30]$. Here, we’ve added value 30 to elements between indices 2 and 3. Note the index of the list starts from 1.

• Time complexity: $O(n^2)$
#!/bin/python3
# Input: the first line will contain two integer n and m seperated by a single space.
#  - Next m lines will contain three integers a,b and k separated by a single space.
#  - Numbers in list are numbered from 1 to n.
# Output: print in a single line the maximum value in the updated list.

import sys

if __name__ == "__main__":
n, m = input().strip().split(' ')
n, m = [int(n), int(m)]
arr = [0]*n
for a0 in range(m):
a, b, k = input().strip().split(' ')
a, b, k = [int(a), int(b), int(k)]
for i in range(a-1,b):
arr[i] += k

print (max(arr))


• Time complexity: $O(n)$
#!/bin/python3
# Input: the first line will contain two integer n and m seperated by a single space.
#  - Next m lines will contain three integers a,b and k separated by a single space.
#  - Numbers in list are numbered from 1 to n.
# Output: print in a single line the maximum value in the updated list.

import sys
from itertools import accumulate

if __name__ == "__main__":
n, m = input().strip().split(' ')
n, m = [int(n), int(m)]
arr = [0]*(n+1)
for a0 in range(m):
a, b, k = input().strip().split(' ')
a, b, k = [int(a), int(b), int(k)]
arr[a-1] += k # Save one time and accumulate it later
arr[b] -= k

'''
max = x = 0
for i in arr:
x = x+i
if max < x:
max = x
'''
print (max(accumulate(arr)))


Tags:

Categories:

Updated: