Trim that distracting background off!



Isn't it annoying when you're taking a picture, but the background detracts from the actual substance of the image? I'd say it is. I need to know how much I should crop so that I get rid of this problem! But - as usual - I am quite lazy, so I need someone to do this for me...

Task & Rules

Given a binary matrix representing the image, output the dimensions (width and height) of the smallest sub-matrix that contains all the \$1\$s in the original matrix. A sub-matrix is a block of adjacent entries from the original matrix. Equivalently, it is a new matrix formed by overlapping a subset of adjacent rows and a subset of adjacent columns of the original.

  • It is allowed to take the width and the height of the matrix as input as well.
  • The input is guaranteed to contain at least one \$1\$.
  • You can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is , so try to complete the task in the least bytes you can manage in your language of choice.


$$\left[\begin{matrix} \color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0\\ \color{red}0&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}0&\color{blue}0\\ \color{red}0&\color{blue}1&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}1\\ \color{red}0&\color{blue}0&\color{blue}1&\color{blue}0&\color{blue}1&\color{blue}0\\ \color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0&\color{red}0\end{matrix}\right] \longrightarrow \left[\begin{matrix}1&0&1&0&0\\1&1&0&1&1\\0&1&0&1&0\end{matrix}\right]\longrightarrow(5,3)$$

Test cases

Input | Output

--> (5,1) or (1,5)

--> (3,2) or (2,3)

--> (4,4)

--> (5,1) or (1,5)

--> (3,3)

--> (5,3) or (3,5)

Mr. Xcoder

Posted 2018-10-27T21:55:30.567

Reputation: 39 774

1This feels very familiar; was it in the Sandbox for a while? – Shaggy – 2018-10-27T23:00:23.073

8This is indeed very close to the linked question but I think it can be considered a distant enough subset thereof because generating the matrix is not absolutely necessary for computing the actual width and height. For instance, one possible algorithm would be to count the minimal number of marginal zeros for each row and column and subtract those from the original dimensions. – Mr. Xcoder – 2018-10-28T10:08:48.680

related - Highlight the Bounding Box, Part I: Cartesian Grid – Jonathan Allan – 2018-10-28T13:57:44.820



MATL, 5 bytes


Try it online! Or verify all test cases.


JYa   % Implicit input. Unpad matrix. This removes outer zeros
Zy    % Size. Implicit display

Luis Mendo

Posted 2018-10-27T21:55:30.567

Reputation: 87 464

9All I see is Yahtzee. – flawr – 2018-10-28T08:49:21.830


Octave, 57 56 45 bytes

Here find does the heavy lifting: It finds the row and colum indices of the nonzero entries. Then we just have to find the difference between the maximum and the minimum (plus one) for each of those seperately.

Thanks @beaker and @AndrasDeak for -1 byte, and @LuisMendo for -11 bytes!


Try it online!


Posted 2018-10-27T21:55:30.567

Reputation: 40 560


APL (Dyalog Unicode), 10 bytesSBCS

Anonymous tacit prefix function.


Try it online!

 indices of 1s.

() apply the following tacit function to that:

⌊/ the minimum (lowest y coordinate and lowest x coordinate)

⌈/- the maximum minus that (this gives us the range)

1+ one plus that (to be inclusive)


Posted 2018-10-27T21:55:30.567

Reputation: 37 779


Python 2, 92 86 bytes

def f(a,L=len):exec"a=zip(*a[1-any(a[0]):])[::-1];"*4*L(a[0])*L(a);return L(a[0]),L(a)

Try it online!

Chas Brown

Posted 2018-10-27T21:55:30.567

Reputation: 8 959


Jelly, 7 bytes


Try it online!

How it works

S,§t€0Ẉ  Main link. Argument: M (matrix)

S        Take the columnwise sum. Let's call the resulting array A.
  §      Take the sum of each row. Let's call the resulting array B.
 ,       Pair; yield [A, B].
   t€0   Trim surrounding zeroes of A and B.
      Ẉ  Widths; yields the lengths of the trimmed arrays.


Posted 2018-10-27T21:55:30.567

Reputation: 196 637


Python 2,  63  55 bytes

-8 with help from Vincent (take the input matrix as a Numpy array)

lambda a:[len(`a.max(x)`[7::3].strip('0'))for x in 0,1]

An unnamed function accepting a 2-d Numpy array of integers (in {0,1}) which returns a list of integers, [width,height].

Try it online!

Non-Numpy version in 63 bytes (accepting a list of lists of integers in {0,1}):

lambda a:[len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a]

Try it online!


Given a matrix, a, for each (v) of the transpose, zip(*a), and a itself we find the height required (given the transpose this is the width).

Mapping max across v yields a list of zeros and ones, representing if each row of v contains any ones. The string representation of this list is found using backticks (`...`), this gives a string with a leading [, then the zeros and ones delimited by , (comma+space). We slice this string starting at index one in steps of three using [1::3] getting us a string of only the zeros and ones, which allows us to use the string function strip to remove the outer zeros (strip('0')).

For example:

      a = [[0,0,0,0,0]           map(max,a)                    = [0,1,1]
          ,[0,1,0,0,0]          `map(max,a)`[1::3]             = '011'
          ,[0,0,0,1,0]]         `map(max,a)`[1::3].strip('0')  = '11'
                            len(`map(max,a)`[1::3].strip('0')) = 2

zip(*a) = [(0,0,0)         map(max,zip(*a))                    = [0,1,0,1,0]
          ,(0,1,0)        `map(max,zip(*a))`[1::3]             = '01010'
          ,(0,0,0)        `map(max,zip(*a))`[1::3].strip('0')  = '101'
          ,(0,0,1)    len(`map(max,zip(*a))`[1::3].strip('0')) = 3

    --> [len(`map(max,v)`[1::3].strip('0'))for v in zip(*a),a] = [3,2]

Jonathan Allan

Posted 2018-10-27T21:55:30.567

Reputation: 67 804

57 bytes using a numpy array. – Vincent – 2018-10-29T13:27:46.167

If we take input as a non-built-in type shouldn't we be counting some kind of import statement to allow us to do so? (It might be just that we have to title the post as "Python 2 with numpy" - I'm not entirely sure) ...if you have some time could you ask in the nineteenth byte chat room? – Jonathan Allan – 2018-10-29T13:35:23.253


...also 55 bytes right?

– Jonathan Allan – 2018-10-29T13:37:18.137


I couldn't really find a clear answer on PPCG Meta, so I'm not sure about this. And yes, 55 bytes indeed :)

– Vincent – 2018-10-29T13:47:08.583


I just asked. According to this post, the import doesn't have to be included.

– Vincent – 2018-10-29T14:11:49.910


Retina 0.8.2, 83 bytes


$#1 $.2

Try it online! Explanation:


Delete leading and trailing zero rows.


Remove all 0s on the lines above the last. Remove all the 1s two, but change the digit underneath on the next line to a 1 in that case. This bitwise or's the rows together.

$#1 $.2

Count the number of rows as the number of newlines plus 1 and the number of columns as the number of digits between the first and last 1.


Posted 2018-10-27T21:55:30.567

Reputation: 95 035


J, 31 bytes


Try it online!


                            ^:_ - repeat until the result stops changing
   (                    )^:4    - repeat 4 times
             ^:(        )       - is
                  1#.           - the sum of
                      {.        - the first row
                 =              - equal 
                0               - to 0
           }.                   - if yes, drop the first row
    [:|.@|:                     - transpose and reverse (rotate 90 degrees) 
[:$                             - what's the shape of the result?

Galen Ivanov

Posted 2018-10-27T21:55:30.567

Reputation: 13 815


q/kdb+, 16 bytes


Thomas Smyth

Posted 2018-10-27T21:55:30.567

Reputation: 111


Mathematica, 34 bytes


Pure function. Takes a nested list of integers as input, and returns a list of two integers (the height followed by the width) as output. The Unicode character is U+F3C7 for \[Transpose].


Posted 2018-10-27T21:55:30.567

Reputation: 15 731


R, 48 46 bytes


Try it online!

-2 bytes saved by Giuseppe.

Kirill L.

Posted 2018-10-27T21:55:30.567

Reputation: 6 693


05AB1E, 11 9 bytes


-2 bytes thanks to @Mr.Xcoder.

Try it online or verify all test cases.


ζ            # Swap the rows and columns of the (implicit) input-list
 ‚           # Pair it with the (implicit) input-list
  O          # Take the sum of each column and row
   ε         # Map Both the list of column-sums and list of row-sums to:
    0Û       #  Remove all leading zeros
      0Ü     #  Remove all trailing zeros
        g    #  Take the length of the remaining lists

Kevin Cruijssen

Posted 2018-10-27T21:55:30.567

Reputation: 67 575

1ζ‚Oε0Û0Üg saves 2 bytes. – Mr. Xcoder – 2018-10-29T10:39:31.107

@Mr.Xcoder Ah, of course. I was already not too happy about that swap. Can't believe I hadn't thought about doing the pair first and than the sum.. >.> – Kevin Cruijssen – 2018-10-29T10:44:54.920


Japt, 16 15 bytes


Try it or run all test cases


[   ]               :Create an array containing
 U                  : The input and
  Uy                : The input transposed
     ®              :Map each Z
       ð            : Indices of elements where
        d           :  Any element is truthy (not 0)
      =  )          : Reassign to Z
          Î         : First element
           a        : Absolute difference with
            ZÌ      :  Last element
              Ä     :   Plus 1


Posted 2018-10-27T21:55:30.567

Reputation: 24 623


Jelly, 9 bytes


Try it online!

Erik the Outgolfer

Posted 2018-10-27T21:55:30.567

Reputation: 38 134


Haskell, 76 bytes

f x=length.s.reverse.s<$>[foldr(zipWith(:))e x,x]

Try it online!


Posted 2018-10-27T21:55:30.567

Reputation: 23 676


Ruby, 60 bytes


Try it online!


Posted 2018-10-27T21:55:30.567

Reputation: 11 099