Clever Geek Handbook

2d, crop with set value

What's a good way to trim a 2d array with a given 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 trimming operation must be removed from any of the four sides.

+3


source to share


1 answer


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)


Complexity of time O(WIDTH * HEIGHT)

, complexity of space O(1)

.

In some programming languages ​​(like C or C ++), the loop for

should be much faster due to the locality of the reference and vectorization .

0


source






More articles:


All Articles