Given a 2D array plates[][] of size N, which each row representing the length and width of a N rectangular plates, the task is to find the maximum number of plates that can be placed on one another.
Note: A plate can be put on another only if its length and width are strictly smaller than that plate.
Examples:
Input: Plates[][] = [ [3, 5], [6, 7], [7, 2], [2, 3] ]
Output: 3
Explanation: Plates can be arranged in this manner [ 6, 7 ] => [ 3, 5 ] => [ 2, 3 ].Input: Plates[][] = [ [6, 4], [ 5, 7 ], [1, 2], [ 3, 3 ], [ 7, 9 ] ]
Output: 4
Explanation: Plates can be arranged in this manner [ 7, 9 ] => [ 5, 7 ] => [ 3, 3 ] => [ 1, 2 ].
Approach: The problem is a variation of the Longest increasing subsequence problem. The only difference is that in LIS, if i < j, then ith element will always come before the jth element. But here, choosing of plates doesn’t depend on index. So, to get this index restriction, sorting all the plates in decreasing order of area is required.
If (i < j) and area of ith plate is also greater than jth plate, then ith plate will always come before(down) the jth plate.
Recursive approach:
Two possible choices exists for each plate, i.e. either to include it in the sequence or discard it. A plate can be included only when its length and width are smaller than the previous included plate.
Recursion tree for the array plates[][] = [ [6, 7], [3, 5], [7, 2] ] is as follows:
Below is the implementation of the recursive approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Comparator function to sort plates// in decreasing order of areabool comp(vector<int> v1, vector<int> v2){ return v1[0] * v1[1] > v2[0] * v2[1];}// Recursive function to count and return// the max number of plates that can be placedint countPlates(vector<vector<int> >& plates, int lastLength, int lastWidth, int i, int n){ // If no plate remains if (i == n) return 0; int taken = 0, notTaken = 0; // If length and width of previous plate // exceeds that of the current plate if (lastLength > plates[i][0] && lastWidth > plates[i][1]) { // Calculate including the plate taken = 1 + countPlates(plates, plates[i][0], plates[i][1], i + 1, n); // Calculate excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); } // Otherwise else // Calculate only excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); return max(taken, notTaken);}// Driver codeint main(){ vector<vector<int> > plates = { { 6, 4 }, { 5, 7 }, { 1, 2 }, { 3, 3 }, { 7, 9 } }; int n = plates.size(); // Sorting plates in decreasing order of area sort(plates.begin(), plates.end(), comp); // Assuming first plate to be of maximum size int lastLength = INT_MAX; int lastWidth = INT_MAX; cout << countPlates(plates, lastLength, lastWidth, 0, n); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{// Recursive function to count and return// the max number of plates that can be placedstatic int countPlates(int[][] plates, int lastLength, int lastWidth, int i, int n){ // If no plate remains if (i == n) return 0; int taken = 0, notTaken = 0; // If length and width of previous plate // exceeds that of the current plate if (lastLength > plates[i][0] && lastWidth > plates[i][1]) { // Calculate including the plate taken = 1 + countPlates(plates, plates[i][0], plates[i][1], i + 1, n); // Calculate excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); } // Otherwise else // Calculate only excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); return Math.max(taken, notTaken);}// Driver codepublic static void main(String[] args){ int[][] plates = { { 6, 4 }, { 5, 7 }, { 1, 2 }, { 3, 3 }, { 7, 9 } }; int n = plates.length; // Sorting plates in decreasing order of area Arrays.sort(plates, (v1, v2)-> (v2[0] * v2[1]) - (v1[0] * v1[1])); // Assuming first plate to be of maximum size int lastLength = Integer.MAX_VALUE; int lastWidth = Integer.MAX_VALUE; System.out.println(countPlates(plates, lastLength, lastWidth, 0, n));}}// This code is contributed by offbeat |
Python3
from functools import reducefrom operator import mul# Recursive function to count and return# the max number of plates that can be placeddef countPlates(plates, lastLength, lastWidth, i, n): # If no plates remains if i == n: return 0 taken = 0 not_taken = countPlates(plates, lastLength, lastWidth, i+1, n) # If length and width of previous plates # exceeds that of the current plate if lastLength > plates[i][0] and lastWidth > plates[i][1]: # Calculating including plate taken = 1 + countPlates(plates, plates[i][0], plates[i][1], i+1, n) # Otherwise else: # Calculate excluding the plate not_taken = countPlates(plates, lastLength, lastWidth, i+1, n) return max(taken, not_taken)plates = [(6, 4), (5, 7), (1, 2), (3, 3), (7, 9)]n = len(plates)# Sorting plates in decreasing order of areaplates.sort(key= lambda tup: reduce(mul, tup), reverse=True)lastlength = pow(10, 9)lastwidth = pow(10, 9)print(countPlates(plates, lastlength, lastwidth, 0, n))# This code is contributed by sdeadityasharma. |
C#
// C# code to implement the approachusing System;using System.Linq;class GFG { // Recursive function to count and return // the max number of plates that can be placed static int countPlates(int[][] plates, int lastLength, int lastWidth, int i, int n) { // If no plate remains if (i == n) return 0; int taken = 0, notTaken = 0; // If length and width of previous plate // exceeds that of the current plate if (lastLength > plates[i][0] && lastWidth > plates[i][1]) { // Calculate including the plate taken = 1 + countPlates(plates, plates[i][0], plates[i][1], i + 1, n); // Calculate excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); } // Otherwise else // Calculate only excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); return Math.Max(taken, notTaken); } // Driver code public static void Main(string[] args) { int[][] plates = { new int[] { 6, 4 }, new int[] { 5, 7 }, new int[] { 1, 2 }, new int[] { 3, 3 }, new int[] { 7, 9 } }; int n = plates.Length; // Sorting plates in decreasing order of area Array.Sort(plates, (v1, v2) => (v2[0] * v2[1]) - (v1[0] * v1[1])); // Assuming first plate to be of maximum size int lastLength = Int32.MaxValue; int lastWidth = Int32.MaxValue; Console.WriteLine(countPlates(plates, lastLength, lastWidth, 0, n)); }}// This code is contributed by phasing17 |
Javascript
<script>// Javascript Program for the above approach// Recursive function to count and return// the max number of plates that can be placedfunction countPlates(plates, lastLength, lastWidth, i, n){ // If no plate remains if (i == n) return 0; var taken = 0, notTaken = 0; // If length and width of previous plate // exceeds that of the current plate if (lastLength > plates[i][0] && lastWidth > plates[i][1]) { // Calculate including the plate taken = 1 + countPlates(plates, plates[i][0], plates[i][1], i + 1, n); // Calculate excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); } // Otherwise else // Calculate only excluding the plate notTaken = countPlates(plates, lastLength, lastWidth, i + 1, n); return Math.max(taken, notTaken);}// Driver codevar plates = [ [ 6, 4 ], [ 5, 7 ], [ 1, 2 ], [ 3, 3 ], [ 7, 9 ] ];var n = plates.length;// Sorting plates in decreasing order of areaplates.sort((v1, v2) => v2[0] * v2[1] - v1[0] * v1[1]);// Assuming first plate to be of maximum sizevar lastLength = 1000000000;var lastWidth = 1000000000;document.write(countPlates(plates, lastLength, lastWidth, 0, n));// This code is contributed by rutvik_56</script> |
Output:
4
Time Complexity: O(2N)
Auxiliary Space: O(N)
Dynamic Programming Approach: The above approach can be optimized using Dynamic programming as illustrated below.
Below is the implementation of the above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Comparator function to sort plates// in decreasing order of areabool comp(vector<int> v1, vector<int> v2){ return v1[0] * v1[1] > v2[0] * v2[1];}// Function to count and return the max// number of plates that can be placedint countPlates(vector<vector<int> >& plates, int n){ // Stores the maximum // number of plates int maximum_plates = 1; vector<int> dp(n, 1); for (int i = 1; i < n; i++) { int cur = dp[i]; // For each i-th plate, traverse // all the previous plates for (int j = i - 1; j >= 0; j--) { // If i-th plate is smaller than j-th plate if (plates[i][0] < plates[j][0] && plates[i][1] < plates[j][1]) { // Include the j-th plate only if current // count exceeds the previously stored count if (cur + dp[j] > dp[i]) { dp[i] = cur + dp[j]; // Update the maximum count maximum_plates = max(maximum_plates, dp[i]); } } } } return maximum_plates;}// Driver codeint main(){ vector<vector<int> > plates = { { 6, 4 }, { 5, 7 }, { 1, 2 }, { 3, 3 }, { 7, 9 } }; int n = plates.size(); // Sorting plates in decreasing order of area sort(plates.begin(), plates.end(), comp); cout << countPlates(plates, n); return 0;} |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ // Function to count and return the max // number of plates that can be placed static int countPlates(ArrayList<plate> plates, int n) { // Stores the maximum // number of plates int maximum_plates = 1; ArrayList<Integer> dp = new ArrayList<Integer>(); for(int i = 1 ; i <= n ; i++){ dp.add(1); } for (int i = 1; i < n; i++) { int cur = dp.get(i); // For each i-th plate, traverse // all the previous plates for (int j = i - 1 ; j >= 0 ; j--){ // If i-th plate is smaller than j-th plate if (plates.get(i).l < plates.get(j).l && plates.get(i).b < plates.get(j).b) { // Include the j-th plate only if current // count exceeds the previously stored count if (cur + dp.get(j) > dp.get(i)) { dp.set(i, cur + dp.get(j)); // Update the maximum count maximum_plates = Math.max(maximum_plates, dp.get(i)); } } } } return maximum_plates; } // Driver code public static void main(String args[]) { ArrayList<plate> plates = new ArrayList<plate>( List.of( new plate( 6, 4 ), new plate( 5, 7 ), new plate( 1, 2 ), new plate( 3, 3 ), new plate( 7, 9 ) ) ); int n = plates.size(); // Sorting plates in decreasing order of area Collections.sort(plates, new comp()); System.out.println(countPlates(plates, n)); }}// Class for storing length and breadth of plateclass plate{ int l, b; plate(int l,int b){ this.l = l; this.b = b; }}class comp implements Comparator<plate>{ // Comparator function to sort plates // in decreasing order of area public int compare(plate o1, plate o2){ int x1 = o1.l*o1.b; int x2 = o2.l*o2.b; return x2-x1; }}// This code is contributed by subhamgoyal2014. |
Python3
# codeprint("GFG") |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to count and return the max // number of plates that can be placed static int countPlates(List<plate> plates, int n) { // Stores the maximum // number of plates int maximum_plates = 1; List<int> dp = new List<int>(); for (int i = 1; i <= n; i++) { dp.Add(1); } for (int i = 1; i < n; i++) { int cur = dp[i]; // For each i-th plate, traverse // all the previous plates for (int j = i - 1; j >= 0; j--) { // If i-th plate is smaller than j-th plate if (plates[i].l < plates[j].l && plates[i].b < plates[j].b) { // Include the j-th plate only if current // count exceeds the previously stored count if (cur + dp[j] > dp[i]) { dp[i] = cur + dp[j]; // Update the maximum count maximum_plates = Math.Max(maximum_plates, dp[i]); } } } } return maximum_plates; } // Driver code public static void Main(string[] args) { List<plate> plates = new List<plate> { new plate(6, 4), new plate(5, 7), new plate(1, 2), new plate(3, 3), new plate(7, 9) }; int n = plates.Count(); // Sorting plates in decreasing order of area plates = plates.OrderByDescending(x => x.l * x.b).ToList(); Console.WriteLine(countPlates(plates, n)); }}// Class for storing length and breadth of plateclass plate{ public int l, b; public plate(int l, int b) { this.l = l; this.b = b; }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript program for the above approach// Function to count and return the max// number of plates that can be placedfunction countPlates(plates, n){ // Stores the maximum // number of plates var maximum_plates = 1; var dp = Array(n).fill(1); for(var i = 1; i < n; i++) { var cur = dp[i]; // For each i-th plate, traverse // all the previous plates for(var j = i - 1; j >= 0; j--) { // If i-th plate is smaller than j-th plate if (plates[i][0] < plates[j][0] && plates[i][1] < plates[j][1]) { // Include the j-th plate only if // current count exceeds the // previously stored count if (cur + dp[j] > dp[i]) { dp[i] = cur + dp[j]; // Update the maximum count maximum_plates = Math.max( maximum_plates, dp[i]); } } } } return maximum_plates;}// Driver codevar plates = [ [ 6, 4 ], [ 5, 7 ], [ 1, 2 ], [ 3, 3 ], [ 7, 9 ] ];var n = plates.length;// Sorting plates in decreasing order of areaplates.sort((v1, v2) => { return((v2[0] * v2[1]) - (v1[0] * v1[1]));});document.write(countPlates(plates, n));// This code is contributed by noob2000</script> |
Output:
4
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
