Find largest sub-matrix with all 1s (not necessarily square)

 Posted on January 1, 2012  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix. Example: > > > > 1 1 0 0 1 0 > > > > > 0 1 1 1 1 1 > > > > > 1 1 1 1 1 0 > > > > > 0 0 1 1 0 0 > > ```Largest all 1s sub-matrix is from (1,1) to (2,4). [Read More]
kodeknight  rectangle 

Maximum Area Rectangle in Histogram

 Posted on January 1, 2012  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram. (Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.) Consider the histogram below: Max area of the rectangle: Max area = 4 * 3 = 12 [Read More]
kodeknight  rectangle  hard  stack  histogram 

Program to check if two rectangle overlap or itntersect

 Posted on May 14, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Input - 2 Rectangles with x and y coordinates. Output - boolean value which states if they overlap or not This is a one of the classic problems in graphics programming and game development. So, let’s see how we can solve it. Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen. [Read More]
Algorithms  kodeknight  rectangle  incomplete  geometric-search  java 

Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife ?

 Posted on December 3, 2009  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

 The cut (plane) should pass through the center of the two rectangles: the outer cake and the inner hollow area. Since any plane passing through the center of the cuboid will divide the volume in two halves, both the cake and hollow area are divided into two equal halves.

kodeknight  logical questions  rectangle