CODEWITHSUNDEEP
arraysalgorithm
sagar kumar
sagar kumar

Reputation: 29

given a 2D matrix with range of blocks occupied for each column,find the number of blocks occupied for each row

we have a nXn matrix. we have given a n lines of input. each line i(starting from 0) has two integers l & r which is corresponding to column i and specifies that the block in that column is occupied in the range from l to r(0 indexing).

we have to find the number of blocks in that 2d matrix for every row using another array to store the value for each row number. for example, we are given n=5. and input are,

1 3
2 3
1 3
2 3
1 2

we have to give an array of size n, with each index giving the number of blocks occupied by that corresponding row in the 2 d matrix. for example in the above case, the 2 D matrix will look like

0 0 0 0 0
1 1 1 1 0
1 1 1 1 1
1 0 1 0 1
0 0 0 0 0

(0 represents unoccupied and 1 represents occupied) ans will be 0 3 5 4 0

I am able to do this in o(n^2).

Is there any way we can do it in O(n)???

Upvotes: 2

Views: 206

Answers (2)

Adeel Zafar Soomro
Adeel Zafar Soomro

Reputation: 1522

@Aivean has the right algorithm. It can be simplified just a little bit further if one makes the following observation.

Each block pair, say [p q], introduces an increment for the interval beginning at index p (inclusive) and ending at index q + 1 (exclusive). This means that one could maintain a single array, say deltas, and, for each block pair, increment deltas[p] and decrement deltas[q + 1], if it exists.

To get the desired result of number of occupied blocks per row, one would generate an array of cumulative sums over the deltas.

Here is an implementation of the algorithm in Javascript:

var m = [[1, 3],
         [2, 3],
         [1, 3],
         [2, 3],
         [1, 2]];

m.reduce(
    function (deltas, pair) {
        /* For each block (pair) in the matrix,
           increment the delta for the beginning row (inclusive). */
        ++deltas[pair[0]];
        /* Decrement the delta for the row after the ending row (exclusive),
           if it exists. */
        pair[1] + 1 < m.length && --deltas[pair[1] + 1];
        return deltas;
    },
    /* Generate an array of zeroes as the initial value of deltas. */
    m.map(Number.prototype.valueOf, 0))
.reduce(
    function (acc, delta) {
        /* Find the cumulative sum from each delta, starting with zero. */
        delta += acc[acc.length - 1] || 0;
        /* Build up an array of cumulative sums. */
        acc.push(delta);
        return acc;
    }, []);

Here is the resulting value of this computation:

[0, 3, 5, 4, 0]

The above code calls map once and reduce twice, each an O(N) operation.

Upvotes: 0

Aivean
Aivean

Reputation: 10882

Yes, you can.

The idea is that knowing how many cells are occupied for current row and knowing how may intervals starts and ends at the next row you can easily calculate the occupancy for the next row: occupiednext = occupiedprev + starts - ends.

Updated: I came up with much simpler solution.

Create two int arrays of size N, name them begins and ends. Initialize all of them with zeroes. For each interval, increment begins array at index that corresponds to the interval starting index and decrement ends at interval end index: begins[intervalStart]++ ends[intervalEnd]--.

Create counter occupied=0. Now loop rowIndex from 0 to N-1. For each iteration occupied = occupied + begins[rowIndex] + ends[rowIndex-1] (check for the array boundaries carefully). After that occupied will hold the exact number of occupied cells for your current row (rowIndex).

Upvotes: 2

Related Questions