Given an array arr containing N unique integers. The task is to calculate the minimum number of deques required to make the array sorted.
Example:
Input: arr[] = {3, 6, 0, 9, 5, 4}
Output: 2
Explanation:
Create a new deque d1 = {3}.
Create a new deque d2 = {6}.
Push 0 onto the front of d1; d1 = {0, 3}
Push 9 onto the back of d2; d2 = {6, 9}
Push 5 onto the front of d2; d2 = {5, 6, 9}
Push 4 onto the front of d2; d2 = {4, 5, 6, 9}
Hence 2 minimum 2 deques are required.Input: arr[] = {50, 45, 55, 60, 65, 40, 70, 35, 30, 75}
Output: 1
Approach: The above problem can be solved greedily. Follow the below steps to solve the problem:
- Create two arrays fronts and backs which will store the front and back elements of all deques.
- Iterate for all elements in the array. For each element arr[i], the current element can be pushed in a pre-existing deque if:
- There exists a fronts[j] which is greater than arr[i] because this means that this arr[i] can be pushed in the front of this deque. But if there exists another element in between arr[i] and fronts[j] in the array arr, then it cannot be pushed because pushing will disturb the order of elements in deques such that these deques cannot be arranged in the form of a sorted array, even being individually sorted.
- Similarly, check for the array backs using the above-mentioned step.
- If an element cannot be pushed to an of the deque then another deque should be created for that element. So push the element in fronts as well as in backs array because it is both the front and back of the newly created deque.
- Now, return the size of array fronts (or backs) as the answer to this question.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;int minDeques(vector<int> arr){ // Vectors to store the front and back // element of all present deques vector<int> fronts, backs; // Iterate through all array elements for (int i = 0; i < arr.size(); i++) { // Bool variable to check if the array // element has already been pushed or not bool hasBeenPushed = false; for (int j = 0; j < fronts.size(); j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { bool isSafe = true; for (int k = 0; k < arr.size(); k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { bool isSafe = true; for (int k = 0; k < arr.size(); k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.push_back(arr[i]); backs.push_back(arr[i]); } } return fronts.size();}// Driver Codeint main(){ vector<int> arr = { 3, 6, 0, 9, 5, 4 }; cout << minDeques(arr);} |
Java
// Java program for the above approachimport java.util.*;class GFG{public static int minDeques(int[] arr){ // Vectors to store the front and back // element of all present deques ArrayList<Integer> fronts = new ArrayList<Integer>(); ArrayList<Integer> backs = new ArrayList<Integer>(); // Iterate through all array elements for (int i = 0; i < arr.length; i++) { // Bool variable to check if the array // element has already been pushed or not boolean hasBeenPushed = false; for (int j = 0; j < fronts.size(); j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts.get(j)) { boolean isSafe = true; for (int k = 0; k < arr.length; k++) { if (arr[i] < arr[k] && arr[k] < fronts.get(j)) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts.set(j, arr[i]); hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs.get(j)) { Boolean isSafe = true; for (int k = 0; k < arr.length; k++) { if (arr[i] > arr[k] && arr[k] > backs.get(j)) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs.set(j, arr[i]); hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.add(arr[i]); backs.add(arr[i]); } } return fronts.size();}// Driver Codepublic static void main(String args[]){ int[] arr = { 3, 6, 0, 9, 5, 4 }; System.out.println(minDeques(arr));}}// This code is contributed by saurabh_jaiswal.. |
Python3
# python program for the above approachdef minDeques(arr): # Vectors to store the front and back # element of all present deques fronts = [] backs = [] # Iterate through all array elements for i in range(0, len(arr)): # Bool variable to check if the array # element has already been pushed or not hasBeenPushed = False for j in range(0, len(fronts)): # Check for all deques where arr[i] # can be pushed in the front if (arr[i] < fronts[j]): isSafe = True for k in range(0, len(arr)): if (arr[i] < arr[k] and arr[k] < fronts[j]): isSafe = False break # Push in front of an already # existing deque if (isSafe): fronts[j] = arr[i] hasBeenPushed = True break # Check for all deques where arr[i] # can be pushed in the back if (arr[i] > backs[j]): isSafe = True for k in range(0, len(arr)): if (arr[i] > arr[k] and arr[k] > backs[j]): isSafe = False break # Push in back of an already # existing deque if (isSafe): backs[j] = arr[i] hasBeenPushed = True break # If arr[i] cannot be pushed to any # of the existing deques, then push # it in a new deque if (not hasBeenPushed): fronts.append(arr[i]) backs.append(arr[i]) return len(fronts)# Driver Codeif __name__ == "__main__": arr = [3, 6, 0, 9, 5, 4] print(minDeques(arr)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { static int minDeques(List<int> arr) { // Vectors to store the front and back // element of all present deques List<int> fronts = new List<int>(); List<int> backs = new List<int>(); // Iterate through all array elements for (int i = 0; i < arr.Count; i++) { // Bool variable to check if the array // element has already been pushed or not bool hasBeenPushed = false; for (int j = 0; j < fronts.Count; j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { bool isSafe = true; for (int k = 0; k < arr.Count; k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { bool isSafe = true; for (int k = 0; k < arr.Count; k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.Add(arr[i]); backs.Add(arr[i]); } } return fronts.Count; } // Driver Code public static void Main() { List<int> arr = new List<int>{ 3, 6, 0, 9, 5, 4 }; Console.WriteLine(minDeques(arr)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approachfunction minDeques(arr) { // Vectors to store the front and back // element of all present deques let fronts = [], backs = []; // Iterate through all array elements for (let i = 0; i < arr.length; i++) { // let variable to check if the array // element has already been pushed or not let hasBeenPushed = false; for (let j = 0; j < fronts.length; j++) { // Check for all deques where arr[i] // can be pushed in the front if (arr[i] < fronts[j]) { let isSafe = true; for (let k = 0; k < arr.length; k++) { if (arr[i] < arr[k] && arr[k] < fronts[j]) { isSafe = false; break; } } // Push in front of an already // existing deque if (isSafe) { fronts[j] = arr[i]; hasBeenPushed = true; break; } } // Check for all deques where arr[i] // can be pushed in the back if (arr[i] > backs[j]) { let isSafe = true; for (let k = 0; k < arr.length; k++) { if (arr[i] > arr[k] && arr[k] > backs[j]) { isSafe = false; break; } } // Push in back of an already // existing deque if (isSafe) { backs[j] = arr[i]; hasBeenPushed = true; break; } } } // If arr[i] cannot be pushed to any // of the existing deques, then push // it in a new deque if (!hasBeenPushed) { fronts.push(arr[i]); backs.push(arr[i]); } } return fronts.length;}// Driver Codelet arr = [3, 6, 0, 9, 5, 4];document.write(minDeques(arr));// This code is contributed by saurabh_jaiswal.</script> |
Output
2
Time Complexity: O(N^3)
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!
