I came across below problem related to Matrix Manipulation.
There is a NxN matrix,divided into N * N cells. Each cell has a predefined value. Which would be given as an input. Iteration has to happen K number of times which is also give in the test input. We have to make sure that we pick the optimum/min value of row/column at each iteration. Final output is the cumulative sum of optimum value saved at the end of each iteration.
Steps 1. Sum up the individual row and column and find the min sum of rows and columns, (it could be a row or a column, have to calculate the minimum)
Step 2. Store the sum found above separately
Increment elements of the min. sum row or column. by 1
Repeat steps 1,2,3 from 1 to Kth value
add the sum at each iteration(specified in step2)
Which data structure?
What you need here is a data structure which allows you to efficiently query and update the minimum sum line. The most commonly used for this is a heap https://en.wikipedia.org/wiki/Heap_(data_structure).
For your purposes it's probably best to just implement the simplest kind, an array-based binary heap:
..for implementation details.
M + Nwhere
M, Nare the number of rows and columns.
A, Bwhich store the row and columon objects separately.
N(no. of columns), and increment each object in
B(list of columns) by 1. Do the same if it's a column.
At the end, just return the first element's attribute.
As a side note, there are other heap structure types which have even better time complexity than the binary heap, e.g. binomial trees, Fibonacci heaps etc. These however are far more complicated, and have higher constant-factor overheads as a result. Thus for your project I feel they are not necessary, as many of them need phenomenal data set sizes to justify for the constant factor overhead.
Besides, they all support the same external operations as the binary heap, as defined by the Abstract Data Structure of Heap.
(heapify is an internal operation specific to the binary heap structure. Quite a few of the other ones are theoretically superior as they do this operation implicitly and "lazily")