Array manipulation

Array manipulation in Go

Problem Statement

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

The algorithm O(m * n)

1. The function arrayManipulation takes two parameters: n and queries. n is the size of the array, and queries is a two dimensional slice. Each slice in queries represents an operation that adds a certain value to the array within a certain range [(1, 2) 3 ] .
2. The function first transforms the two dimensional slicequeries into a single dimension slice of Operation structs. Each Operation struct has two fields: addition and indexes. addition is the value that is added to the array, and indexes is a struct that contains the start and end indices of the range.
3. The function then creates a new slice of int32s with the size of n. This slice will store the final result of the array manipulation operations.
4. Next, the function iterates over the operations slice. For each operation, it iterates over the range of indices and adds the addition value to the corresponding elements in the result slice.
5. After all the operations have been applied, the function sorts the result slice in descending order.
6. Finally, the function returns the first element in the result slice, which holds the maximum value inside the slice.

Array manipulation in Go (1)

But my solution was not perfect and perform poorly so have take a look another algorithms in order to improve mine 😊. Thanks to Mirefly, Firegoblin and anupam_codecs I could came with a better algorithm.

Array manipulation in Go (2)

But still it didn’t feel like that was my code but theirs.

The final implementation O(n)

1. The function arrayManipulation takes two parameters: n and queries. n is the size of the array, and queries is a two dimensional slice. Each slice in queries represents an operation that adds a certain value to the array within a certain range.
2. The function first initializes a slice of int64s with the size of n. This slice will store the final result of the array manipulation operations.
3. Next, the function converts the two dimensional slice queries into a single dimension slice of Operation structs. Each Operation struct has three fields: a, b, and k. a is the start index of the range, b is the end index of the range, and k is the value that is added to the array within the range.
4. The function then iterates over the operations slice. For each operation, it adds the k value to the element at index a in the result slice. If b is less than n(the last position at the slice), the function also subtracts the k value from the element at index b + 1 in the result slice.
5. After all the operations have been applied, the function iterates over the result slice and adds each element to the element at the next index. This ensures that the final element in the result slice contains the maximum value in the array.
6. Right after, the function sorts the result slice in descending order
7. Finally returns the first element (Max value in the slice).

Array manipulation in Go (3)

Disclaimer

I thought it was fun to implement the ascending order function with partial applying and closures BUT of course I KNOW it was a little too much.

Ascending order with currying and closures

Resources

Array Manipulation | HackerRank

Google Bard conversation