We have one 2D array, filled with zeros and ones. We have to find the starting point and ending point of all rectangles filled with 0. It is given that rectangles are separated and do not touch each other however they can touch the boundary of the array. A rectangle might contain only one element.
Examples:
input = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
Output:
[
[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]
]
Explanation:
We have three rectangles here, starting from
(2, 3), (3, 1), (5, 3)
Input = [
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1, 0]
]
Output:
[
[0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5],
[3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2],
[7, 6, 7, 6]
]
Step 1: Look for the 0 row-wise and column-wise
Step 2: When you encounter any 0, save its position in output array and using loop change all related 0 with this position in any common number so that we can exclude it from processing next time.
Step 3: When you change all related 0 in Step 2, store last processed 0's location in output array in the same index.
Step 4: Take Special care when you touch the edge, by not subtracting -1 because the loop has broken on the exact location.
Below is the implementation of above approach:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
void findend(int i,int j, vector<vector<int>> &a,
vector<vector<int>> &output,int index)
{
int x = a.size();
int y = a[0].size();
// flag to check column edge case,
// initializing with 0
int flagc = 0;
// flag to check row edge case,
// initializing with 0
int flagr = 0;
int n, m;
for (m = i; m < x; m++)
{
// loop breaks where first 1 encounters
if (a[m][j] == 1)
{
flagr = 1; // set the flag
break;
}
// pass because already processed
if (a[m][j] == 5) continue;
for (n = j; n < y; n++)
{
// loop breaks where first 1 encounters
if (a[m][n] == 1)
{
flagc = 1; // set the flag
break;
}
// fill rectangle elements with any
// number so that we can exclude
// next time
a[m][n] = 5;
}
}
if (flagr == 1)
output[index].push_back(m-1);
else
// when end point touch the boundary
output[index].push_back(m);
if (flagc == 1)
output[index].push_back(n-1);
else
// when end point touch the boundary
output[index].push_back(n);
}
void get_rectangle_coordinates(vector<vector<int>> a)
{
// retrieving the column size of array
int size_of_array = a.size();
// output array where we are going
// to store our output
vector<vector<int>> output;
// It will be used for storing start
// and end location in the same index
int index = -1;
for (int i = 0; i < size_of_array; i++)
{
for (int j = 0; j < a[0].size(); j++)
{
if (a[i][j] == 0)
{
// storing initial position
// of rectangle
output.push_back({i, j});
// will be used for the
// last position
index = index + 1;
findend(i, j, a, output, index);
}
}
}
cout << "[";
int aa = 2, bb = 0;
for(auto i:output)
{
bb = 3;
cout << "[";
for(int j:i)
{
if(bb)
cout << j << ", ";
else
cout << j;
bb--;
}
cout << "]";
if(aa)
cout << ", ";
aa--;
}
cout << "]";
}
// Driver code
int main()
{
vector<vector<int>> tests = {
{1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};
get_rectangle_coordinates(tests);
return 0;
}
// This code is contributed by mohit kumar 29.
// Java program for the above approach
import java.util.*;
class GFG {
static void
findend(int i, int j, int[][] a,
ArrayList<ArrayList<Integer> > output,
int index)
{
int x = a.length;
int y = a[1].length;
// flag to check column edge case,
// initializing with 0
int flagc = 0;
// flag to check row edge case,
// initializing with 0
int flagr = 0;
int n = 0, m = 0;
for (m = i; m < x; m++) {
// loop breaks where first 1 encounters
if (a[m][j] == 1) {
flagr = 1; // set the flag
break;
}
// pass because already processed
if (a[m][j] == 5)
continue;
for (n = j; n < y; n++) {
// loop breaks where first 1 encounters
if (a[m][n] == 1) {
flagc = 1; // set the flag
break;
}
// fill rectangle elements with any
// number so that we can exclude
// next time
a[m][n] = 5;
}
}
if (flagr == 1) {
var arr = output.get(index);
arr.add(m - 1);
output.set(index, arr);
}
else
// when end point touch the boundary
{
var arr = output.get(index);
arr.add(m);
output.set(index, arr);
}
if (flagc == 1) {
var arr = output.get(index);
arr.add(n - 1);
output.set(index, arr);
}
else
// when end point touch the boundary
{
var arr = output.get(index);
arr.add(n);
output.set(index, arr);
}
}
static void get_rectangle_coordinates(int[][] a)
{
// retrieving the column size of array
int size_of_array = a.length;
// output array where we are going
// to store our output
ArrayList<ArrayList<Integer> > output
= new ArrayList<ArrayList<Integer> >();
// It will be used for storing start
// and end location in the same index
int index = -1;
for (int i = 0; i < size_of_array; i++) {
for (int j = 0; j < a[0].length; j++) {
if (a[i][j] == 0) {
// storing initial position
// of rectangle
output.add(new ArrayList<Integer>(
Arrays.asList(i, j)));
// will be used for the
// last position
index = index + 1;
findend(i, j, a, output, index);
}
}
}
System.out.print("[");
int aa = 2, bb = 0;
for (var i : output) {
bb = 3;
System.out.print("[");
for (int j : i) {
if (bb > 0)
System.out.print(j + ", ");
else
System.out.print(j);
bb--;
}
System.out.print("]");
if (aa > 0)
System.out.print(", ");
aa--;
}
System.out.print("]");
}
// Driver code
public static void main(String[] args)
{
int[][] tests = { { 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 0, 0, 0, 0 },
{ 1, 1, 1, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1 } };
get_rectangle_coordinates(tests);
}
}
// This code is contributed by phasing17
# Python program to find all
# rectangles filled with 0
def findend(i,j,a,output,index):
x = len(a)
y = len(a[0])
# flag to check column edge case,
# initializing with 0
flagc = 0
# flag to check row edge case,
# initializing with 0
flagr = 0
for m in range(i,x):
# loop breaks where first 1 encounters
if a[m][j] == 1:
flagr = 1 # set the flag
break
# pass because already processed
if a[m][j] == 5:
pass
for n in range(j, y):
# loop breaks where first 1 encounters
if a[m][n] == 1:
flagc = 1 # set the flag
break
# fill rectangle elements with any
# number so that we can exclude
# next time
a[m][n] = 5
if flagr == 1:
output[index].append( m-1)
else:
# when end point touch the boundary
output[index].append(m)
if flagc == 1:
output[index].append(n-1)
else:
# when end point touch the boundary
output[index].append(n)
def get_rectangle_coordinates(a):
# retrieving the column size of array
size_of_array = len(a)
# output array where we are going
# to store our output
output = []
# It will be used for storing start
# and end location in the same index
index = -1
for i in range(0,size_of_array):
for j in range(0, len(a[0])):
if a[i][j] == 0:
# storing initial position
# of rectangle
output.append([i, j])
# will be used for the
# last position
index = index + 1
findend(i, j, a, output, index)
print (output)
# driver code
tests = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
get_rectangle_coordinates(tests)
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
static void findend(int i,int j,int[, ] a,
List<List<int>> output,int index)
{
int x = a.GetLength(0);
int y = a.GetLength(1);
// flag to check column edge case,
// initializing with 0
int flagc = 0;
// flag to check row edge case,
// initializing with 0
int flagr = 0;
int n = 0, m = 0;
for (m = i; m < x; m++)
{
// loop breaks where first 1 encounters
if (a[m, j] == 1)
{
flagr = 1; // set the flag
break;
}
// pass because already processed
if (a[m, j] == 5) continue;
for (n = j; n < y; n++)
{
// loop breaks where first 1 encounters
if (a[m, n] == 1)
{
flagc = 1; // set the flag
break;
}
// fill rectangle elements with any
// number so that we can exclude
// next time
a[m, n] = 5;
}
}
if (flagr == 1)
output[index].Add(m-1);
else
// when end point touch the boundary
output[index].Add(m);
if (flagc == 1)
output[index].Add(n-1);
else
// when end point touch the boundary
output[index].Add(n);
}
static void get_rectangle_coordinates(int[,] a)
{
// retrieving the column size of array
int size_of_array = a.GetLength(0);
// output array where we are going
// to store our output
List<List<int>> output = new List<List<int>>();
// It will be used for storing start
// and end location in the same index
int index = -1;
for (int i = 0; i < size_of_array; i++)
{
for (int j = 0; j < a.GetLength(1); j++)
{
if (a[i, j] == 0)
{
// storing initial position
// of rectangle
output.Add(new List<int>(new int[] {i, j}));
// will be used for the
// last position
index = index + 1;
findend(i, j, a, output, index);
}
}
}
Console.Write("[");
int aa = 2, bb = 0;
foreach (var i in output)
{
bb = 3;
Console.Write("[");
foreach(int j in i)
{
if(bb > 0)
Console.Write(j + ", ");
else
Console.Write (j);
bb--;
}
Console.Write ("]");
if(aa > 0)
Console.Write(", ");
aa--;
}
Console.Write("]");
}
// Driver code
public static void Main(string[] args)
{
int[, ] tests = {
{1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 1, 1, 1, 1},
{1, 0, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};
get_rectangle_coordinates(tests);
}
}
// This code is contributed by phasing17
<script>
// JavaScript program to find all
// rectangles filled with 0
function findend(i,j,a,output,index){
let x = a.length
let y = a[0].length
let m,n;
// flag to check column edge case,
// initializing with 0
let flagc = 0
// flag to check row edge case,
// initializing with 0
let flagr = 0
for(m=i;m<x;m++){
// loop breaks where first 1 encounters
if(a[m][j] == 1){
flagr = 1 // set the flag
break
}
// pass because already processed
if(a[m][j] == 5)
pass
for(n=j;n<y;n++){
// loop breaks where first 1 encounters
if(a[m][n] == 1){
flagc = 1 // set the flag
break
}
// fill rectangle elements with any
// number so that we can exclude
// next time
a[m][n] = 5
}
}
if(flagr == 1)
output[index].push( m-1)
else
// when end point touch the boundary
output[index].push(m)
if(flagc == 1)
output[index].push(n-1)
else
// when end point touch the boundary
output[index].push(n)
}
function get_rectangle_coordinates(a){
// retrieving the column size of array
let size_of_array = a.length
// output array where we are going
// to store our output
let output = []
// It will be used for storing start
// and end location in the same index
let index = -1
for(let i=0;i<size_of_array;i++){
for(let j=0;j<a[0].length;j++){
if(a[i][j] == 0){
// storing initial position
// of rectangle
output.push([i, j])
// will be used for the
// last position
index = index + 1
findend(i, j, a, output, index)
}
}
}
console.log(output)
}
// driver code
let tests = [
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1]
]
get_rectangle_coordinates(tests)
// This code is contributed by shinjanpatra
</script>
Output[[2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]]
Time Complexity: O(x*y).
Auxiliary Space: O(x*y).
Asked in Intuit
Similar Reads
Path in a Rectangle with Circles
There is a m*n rectangular matrix whose top-left(start) location is (1, 1) and bottom-right(end) location is (m*n). There are k circles each with radius r. Find if there is any path from start to end without touching any circle.The input contains values of m, n, k, r and two array of integers X and
15+ min read
Number of rectangles with given area in an N*M grid
Given three positive integers N, M, and A, the task is to count the number of rectangles with area equal to A present in an M * N grid. Examples: Input: N = 2, M = 2, A = 2 Output: 4 Explanation: In the given grid of size 2 × 2, 2 rectangles of dimension 2 × 1 and 2 rectangles of dimension 1 × 2 can
10 min read
Area of the largest Rectangle without a given point
Given the length L and breadth B of a rectangle and the position of a hole in the rectangle as (X, Y) coordinate, the task is to find the area of largest Rectangle within the given Rectangle such that it does not contain the hole.Note: The rectangle is placed at the origin by two of its side touchin
6 min read
Minimum rectangles to cover all points
Given a 2D array points[][], where points[i] = [xi, yi]. The task is to find the minimum number of rectangles of width `w` or less needed to cover all points in a given 2D array, where each rectangle's lower end is at (x1, 0) and upper end at (x2, y2) with x1 = 0. A point is covered if it's within o
4 min read
Print cells with same rectangular sums in a matrix
Given a matrix of m x n matrix, we need to print all those cells at which sum of sub-matrix ended at this cell and sub-matrix starting at this cell is equal to remaining elements. For better understanding please see below diagram, Examples : Input : mat[][] = {1, 2, 3, 5, 4, 1, 0, 2, 0, 1, 2, 0, 7,
12 min read
Find if two rectangles overlap
Given two rectangles, find if the given two rectangles overlap or not.Note that a rectangle can be represented by two coordinates, top left and bottom right. So mainly we are given following four coordinates. l1: Top Left coordinate of first rectangle. r1: Bottom Right coordinate of first rectangle.
5 min read
Smallest square formed with given rectangles
Given a rectangle of length l and breadth b, we need to find the area of the smallest square which can be formed with the rectangles of these given dimensions. Examples: Input : 1 2 Output : 4 We can form a 2 x 2 square using two rectangles of size 1 x 2. Input : 7 10 Output :4900 Let's say we want
6 min read
Check if a point lies inside a rectangle | Set-2
Given coordinates of bottom-left and top-right corners of a rectangle. Check if a point (x, y) lies inside this rectangle or not. Examples: Input: bottom-left: (0, 0), top-right: (10, 8), point: (1, 5) Output: Yes Input: bottom-left: (-1, 4), top-right:(2, 3), point:(0, 4) Output: No This problem is
6 min read
Coordinates of rectangle with given points lie inside
Given two arrays X[] and Y[] with n-elements, where (Xi, Yi) represent a point on coordinate system, find the smallest rectangle such that all points from given input lie inside that rectangle and sides of rectangle must be parallel to Coordinate axis. Print all four coordinates of an obtained recta
6 min read
Maximum size rectangle binary sub-matrix with all 1s
Given a 2d binary matrix mat[][], the task is to find the maximum size rectangle binary-sub-matrix with all 1's. Examples: Input: mat = [ [0, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 0, 0] ] Output : 8Explanation : The largest rectangle with only 1's is from (1, 0) to (2, 3) which is[1, 1, 1, 1]
15 min read