CODEWITHSUNDEEP
arraysalgorithm
Distraction
Distraction

Reputation: 460

2d array, trim with specified value

What's a good way to trim a 2d array with a specified value?

A = [0 0 0 0 0]
    [1 2 3 0 0]
    [4 0 6 0 0]
    [0 0 0 0 0]

B = trim(A, 0)
// results in:
// B = [1 2 3]
//     [4 0 6]

The trim operation should be able to cut away from any of the four sides.

Upvotes: 4

Views: 193

Answers (1)

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19847

Pseudocode:

trim(array[WIDTH][HEIGHT], trimmed):

    // top left corner will be (xmin, ymin)
    xmin = WIDTH
    ymin = HEIGHT

    // bottom right corner will be (xmax, ymax)
    xmax = -1
    ymax = -1

    for (y = 0; y < HEIGHT; y++):
        for (x = 0; x < WIDTH; x++):
            if (array[x][y] != trimmed):
                if (xmin > x) xmin = x
                if (xmax < x) xmax = x
                if (ymin > y) ymin = y
                if (ymax < y) ymax = y

    if (xmin == WIDTH)
        return an empty array
    else
        return sub-array with top left corner in (xmin, ymin) 
               and bottom right corner in (xmax, ymax)

Time complexity is O(WIDTH * HEIGHT), space complexity is O(1).

In some programming languages (like C or C++) that for loop should be much faster due to locality of reference and vectorization.

Upvotes: 1

Related Questions