Array Manipulation| Array
TASK(hard)
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
EXAMPLE
n=10 queries=[[1,5,3],[4,8,7],[6,9,1]]
Queries are interpreted as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of k between the indices a and b 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 10 after all operations are performed.
Function Description
Complete the function arrayManipulation in the editor below.
arrayManipulation has the following parameters:
- int n - the number of elements in the array
- int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k.
Returns
- int - the maximum value in the resultant array
Input Format
The first line contains two space-separated integers n and m, the size of the array and the number of operations.
Each of the next m lines contains three space-separated integers a, b and k, the left index, right index and summand.
Constraints
3≤n≤107
1≤m≤2*105
1≤a≤b≤n
0≤k≤109
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Explanation
After the first update the list is 100 100 0 0 0.
After the second update list is 100 200 100 100 100.
After the third update list is 100 200 200 200 100. The maximum value is 200.
Solution 1
def arrayManipulation(n, queries, m):
li = []
for j in range(0, m):
p = queries[j][0]
r = queries[j][1]
v = queries[j][2]
lo = []
for i in range(0, n):
lo.append(0)
for i in range(p - 1, r):
lo[i] = lo[i] + v
li.append(lo)
for i in range(1, m):
for j in range(0, n):
li[i][j] = li[i-1][j] + li[i][j]
return max(max(li))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
queries = []
for _ in range(m):
queries.append(list(map(int, input().rstrip().split())))
result = arrayManipulation(n, queries,m)
print(result)
fptr.write(str(result) + '\n')
fptr.close()
Solution 2
def arrayManipulation(n, queries):
arr = [0]*(n+1)
max_value = 0
total_sum = 0
for query in queries:
l = query[0]
h = query[1]
val = query[2]
arr[l-1] = arr[l-1] + val
arr[h] = arr[h]-val
for value in arr:
total_sum = total_sum + value
max_value = max(max_value, total_sum)
return max_value
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
QUERIES = []
for _ in range(m):
QUERIES.append(list(map(int, input().rstrip().split())))
RESULT = arrayManipulation(n, QUERIES)
fptr.write(str(RESULT) + '\n')
fptr.close()
Explanation Steps
1.Use a Difference Array: Initialize a difference array of size n + 1.
2.Apply Operations: For each operation (a, b, k), update the difference array by adding k at index a-1 and subtracting k at index b (if within bounds).
3.Compute Final Array Values: Traverse the difference array to compute the actual values using prefix sums, and track the maximum value encountered.
