Find any possible two coordinates of Rectangle whose two coordinates are given
Given a matrix mat[][] of size N×N where two elements of the matrix are ‘1’ denoting the coordinate of the rectangle and ‘0’ denotes the empty space, the task is to find the other two coordinates of the rectangle.
Note: There can be multiple answers possible for this problem, print any one of them.
Examples:
Input: mat[][] = {{0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}
Output: {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}}
Explanation:
0 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
The coordinates {{0, 2}, {0, 3}, {1, 2}, {1, 3}} forms the rectangleInput: mat[][] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 0, 0}, {0, 0, 0, 0}}
Output: {{1, 0, 1, 0}, {0, 0, 0, 0}, {1, 0, 1, 0}, {0, 0, 0, 0}}
Approach: The remaining coordinate can be found using these given coordinates because some points may have a common row and some might have a common column. Follow the steps below to solve the problem:
- Initialize two pairs, say p1 and p2 to store the position of 1 in the initial matrix mat[].
- Initialize two pairs, say p3 and p4 to store position where new 1 is to be inserted to make it a rectangle.
- Traverse through the matrix using two nested loops and find the pairs p1 and p2.
- Now there are three possible cases:
- If p1.first and p2.first are same in this case adding 1 to p1.first and p2.first gives us p3.first and p4.first while p3.second and p4.second remain the same as p1.second and p2.second respectively.
- If p1.second and p2.second are the same in this case adding 1 to p1.second and p2.second gives us p3.second and p4.second while p3.first and p4.first remains the same as p1.first and p2.first
- If no coordinates are same, then p3.first = p2.first, p3.second = p1.second, p4.first = p1.first and p4.second = p2.second.
- Replace the coordinates of p3 and p4 with 1 and print the matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the remaining // two rectangle coordinates void Create_Rectangle(vector<string> arr, int n) { // Pairs to store the position of given // two coordinates of the rectangle. pair< int , int > p1 = { -1, -1 }; pair< int , int > p2 = { -1, -1 }; // Pairs to store the remaining two // coordinates of the rectangle. pair< int , int > p3; pair< int , int > p4; // Traverse through matrix and // find pairs p1 and p2 for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (arr[i][j] == '1' ) if (p1.first == -1) p1 = { i, j }; else p2 = { i, j }; } } p3 = p1; p4 = p2; // First Case if (p1.first == p2.first) { p3.first = (p1.first + 1) % n; p4.first = (p2.first + 1) % n; } // Second Case else if (p1.second == p2.second) { p3.second = (p1.second + 1) % n; p4.second = (p2.second + 1) % n; } // Third Case else { swap(p3.first, p4.first); } arr[p3.first][p3.second] = '1' ; arr[p4.first][p4.second] = '1' ; // Print the matrix for ( int i = 0; i < n; i++) { cout << arr[i] << endl; } } // Driver code int main() { // Given Input int n = 4; vector<string> arr{ "0010" , "0000" , "1000" , "0000" }; // Function Call Create_Rectangle(arr, n); return 0; } |
Java
// Java program for above approach import java.awt.*; import java.util.*; class GFG{ static class pair<T, V>{ T first; V second; } // Function to find the remaining // two rectangle coordinates static void Create_Rectangle(ArrayList<String> arr, int n) { // Pairs to store the position of given // two coordinates of the rectangle. pair<Integer, Integer> p1 = new pair<>(); p1.first = - 1 ; p1.second= - 1 ; pair<Integer, Integer> p2 = new pair<>(); p2.first = - 1 ; p2.second = - 1 ; // Pairs to store the remaining two // coordinates of the rectangle. pair<Integer,Integer> p3 = new pair<>(); pair<Integer, Integer> p4 = new pair<>(); // Traverse through matrix and // find pairs p1 and p2 for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < n; j++) { if (arr.get(i).charAt(j) == '1' ) if (p1.first == - 1 ) { p1.first =i; p1.second = j; } else { p2.first = i; p2.second = j; } } } p3 = p1; p4 = p2; // First Case if (p1.first.intValue() == (p2.first).intValue()) { p3.first = (p1.first + 1 ) % n; p4.first = (p2.first + 1 ) % n; } // Second Case else if (p1.second.intValue()==(p2.second).intValue()) { p3.second = (p1.second + 1 ) % n; p4.second = (p2.second + 1 ) % n; } // Third Case else { int temp = p3.first; p3.first = p4.first; p4.first = temp; } // Print the matrix for ( int i = 0 ; i < n; i++) { if (i==p3.first){ for ( int j = 0 ;j<n;j++){ if (j==p3.second) System.out.print( '1' ); else System.out.print(arr.get(i).charAt(j)); } } else if (i==p4.first){ for ( int j = 0 ;j<n;j++){ if (j==p4.second) System.out.print( '1' ); else System.out.print(arr.get(i).charAt(j)); } } else System.out.print(arr.get(i)); System.out.println(); } } // Driver Code public static void main(String[] args) { // Given Input int n = 4 ; ArrayList<String> arr = new ArrayList<>(); arr.add( "0010" ); arr.add( "0000" ); arr.add( "1000" ); arr.add( "0000" ); //{ , "0000", "1000", "0000" }; // Function Call Create_Rectangle(arr, n); } } // This code is contributed by hritikrommie. |
Python3
# Python program for the above approach # Function to find the remaining # two rectangle coordinates def Create_Rectangle(arr, n): for i in range (n): arr[i] = [i for i in arr[i]] # Pairs to store the position of given # two coordinates of the rectangle. p1 = [ - 1 , - 1 ] p2 = [ - 1 , - 1 ] # Pairs to store the remaining two # coordinates of the rectangle. p3 = [] p4 = [] # Traverse through matrix and # find pairs p1 and p2 for i in range (n): for j in range (n): if (arr[i][j] = = '1' ): if (p1[ 0 ] = = - 1 ): p1 = [i, j] else : p2 = [i, j] p3 = p1 p4 = p2 # First Case if (p1[ 0 ] = = p2[ 0 ]): p3[ 0 ] = (p1[ 0 ] + 1 ) % n p4[ 0 ] = (p2[ 0 ] + 1 ) % n # Second Case elif (p1[ 1 ] = = p2[ 1 ]): p3[ 1 ] = (p1[ 1 ] + 1 ) % n p4[ 1 ] = (p2[ 1 ] + 1 ) % n # Third Case else : p3[ 0 ], p4[ 0 ] = p4[ 0 ],p3[ 0 ] arr[p3[ 0 ]][p3[ 1 ]] = '1' arr[p4[ 0 ]][p4[ 1 ]] = '1' # Print the matrix for i in range (n): print ("".join(arr[i])) # Driver code if __name__ = = '__main__' : # Given Input n = 4 arr = [ "0010" , "0000" , "1000" , "0000" ] # Function Call Create_Rectangle(arr, n) # This code is contributed by mohit kumar 29. |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG { static void Create_Rectangle(List< string > arr, int n) { // Pairs to store the position of given // two coordinates of the rectangle. Tuple< int , int > p1 = Tuple.Create(-1, -1); Tuple< int , int > p2 = Tuple.Create(-1, -1); // Pairs to store the remaining two // coordinates of the rectangle. Tuple< int , int > p3, p4; // Traverse through matrix and // find pairs p1 and p2 for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (arr[i][j] == '1' ) { if (p1.Item1 == -1) { p1 = Tuple.Create(i, j); } else { p2 = Tuple.Create(i, j); } } } } p3 = p1; p4 = p2; // First Case if (p1.Item1 == p2.Item1) { p3 = Tuple.Create((p1.Item1 + 1) % n, p1.Item2); p4 = Tuple.Create((p2.Item1 + 1) % n, p2.Item2); } // Second Case else if (p1.Item2 == p2.Item2) { p3 = Tuple.Create(p1.Item1, (p1.Item2 + 1) % n); p4 = Tuple.Create(p2.Item1, (p2.Item2 + 1) % n); } // Third Case else { int temp = p3.Item1; p3 = Tuple.Create(p4.Item1, p3.Item2); p4 = Tuple.Create(temp, p4.Item2); } // Print the matrix for ( int i = 0; i < n; i++) { if (i == p3.Item1) { for ( int j = 0; j < n; j++) { if (j == p3.Item2) Console.Write( "1" ); else Console.Write(arr[i][j]); } Console.WriteLine( " " ); } else if (i == p4.Item1) { for ( int j = 0; j < n; j++) { if (j == p4.Item2) Console.Write( "1" ); else Console.Write(arr[i][j]); } Console.WriteLine( " " ); } else Console.WriteLine(arr[i]); } } // Driver Code static void Main( string [] args) { // Given Input int n = 4; List< string > arr = new List< string >() { "0010" , "0000" , "1000" , "0000" }; // Function Call Create_Rectangle(arr, n); } } // This code is contributed by phasing17. |
Javascript
<script> // JavaScript program for the above approach // Function to find the remaining // two rectangle coordinates function Create_Rectangle(arr, n) { for (let i = 0; i < n; i++) { arr[i] = arr[i].split( "" ) } // Pairs to store the position of given // two coordinates of the rectangle. let p1 = [-1, -1]; let p2 = [-1, -1]; // Pairs to store the remaining two // coordinates of the rectangle. let p3 = []; let p4 = []; // Traverse through matrix and // find pairs p1 and p2 for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (arr[i][j] == '1' ) if (p1[0] == -1) p1 = [i, j]; else p2 = [i, j]; } } p3 = p1; p4 = p2; // First Case if (p1[0] == p2[0]) { p3[0] = (p1[0] + 1) % n; p4[0] = (p2[0] + 1) % n; } // Second Case else if (p1[1] == p2[1]) { p3[1] = (p1[1] + 1) % n; p4[1] = (p2[1] + 1) % n; } // Third Case else { let temp = p3[0]; p3[0] = p4[0]; p4[0] = temp; } arr[p3[0]][p3[1]] = '1' ; arr[p4[0]][p4[1]] = '1' ; // Print the matrix for (let i = 0; i < n; i++) { document.write(arr[i].join( "" ) + "<br>" ); } } // Driver code // Given Input let n = 4; let arr = [ "0010" , "0000" , "1000" , "0000" ]; // Function Call Create_Rectangle(arr, n); </script> |
1010 0000 1010 0000
Time Complexity: O(N2)
Auxiliary Space: O(1)