Rearrange array A[] in non-decreasing order by Swapping A[i] and C[j] if and only if B[i] equals to D[j]
Given arrays A[], B[], C[] and D[] of length N. The task is to output YES/NO by checking if A[] can be rearranged in non-decreasing order using below operation any number of times:
- Swap Ai and Cj if and only if Bi == Dj
Examples:
Input: N = 2, A[] = {3, 2}, B[] = {1, 2}, C[] = {1, 2}. D[] = {1, 1}
Output: YES
Explanation: Let us choose A1 = 3 and C1 = 1. As B1 and D1 both are equal to 1, It means we can swap A1 and C1 with each other. After swapping, updated A[] and C[] are {1, 2} and {3, 2} respectively. It can be seen that A[] is in ascending order now. Thus, output is YES.Input: N = 2, A = {2, 1}, B[] = {2, 1}, C[] = {2, 1}, D[] = {2, 1}
Output: NO
Explanation: It can be verified that it is not possible to make A[] in ascending order using given operation. Therefore, output is NO.
Approach: Implement the idea below to solve the problem
The problem can be solved using HashMap and PriorityQueue. A HashMap is used in which the keys are the elements of B[], D[] and the values are Priority Queues containing the elements of arrays A[] and C[]. Priority Queues are used because they can efficiently return the smallest element.
Step-by-step approach:
- Create a HashMap let say HM, Where the keys are the elements of B[], D[] and the values are Priority Queues containing the elements of A[] and C[].
- First, add elements of array C[] to the HashMap with key as D[]. Then, iterate over array A[] and add its elements to the HashMap if corresponding value of B[] is already present in the HashMap.
- Iterate over array A[] to sort it. For each element, check if its value corresponding to B[] is in the HashMap. If not, check if the element is larger than the previous element. If it’s smaller, set
flag
tofalse
and break the loop because it’s not possible to sort array A[]. - If the Bi corresponding to Ai is present is in the HashMap, retrieve the priority queue for this color and poll elements until you find one that is larger than the previous element. If you can’t find such an element, set
flag
tofalse
and break the loop because it’s not possible to sort array A[]. - After iterating over all elements in array A[]. If
flag
is stilltrue
, output YES else NO.
Below is the implementation of the above approach:
C++
// C++ Implementation #include <iostream> #include <unordered_map> #include <queue> #include <vector> using namespace std; void Check_possibility( int n, vector< long >& A, vector< long >& B, vector< long >& C, vector< long >& D) { unordered_map< long , priority_queue< long >> hm; // Store elements of array C in the map with key as D[i] for ( int i = 0; i < n; i++) { hm[D[i]].push(C[i]); } // Check if A can be sorted given the conditions in B, C, and D long prev = -1; for ( int i = 0; i < n; i++) { if (hm.find(B[i]) == hm.end()) { if (A[i] < prev) { cout << "NO" << endl; return ; } prev = A[i]; } else { priority_queue< long >& pq = hm[B[i]]; while (!pq.empty() && pq.top() < prev) { pq.pop(); } if (pq.empty()) { cout << "NO" << endl; return ; } prev = pq.top(); pq.pop(); } } cout << "YES" << endl; } int main() { int N = 2; vector< long > A = {3, 2}; vector< long > B = {1, 2}; vector< long > C = {1, 2}; vector< long > D = {1, 1}; Check_possibility(N, A, B, C, D); return 0; } // This code is contributed by Tapesh(tapeshdu420) |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; // Driver Class class Main { // Driver Function public static void main(String[] args) throws java.lang.Exception { // Input int N = 2 ; long A[] = { 3 , 2 }; long B[] = { 1 , 2 }; long C[] = { 1 , 2 }; long D[] = { 1 , 1 }; // Function call Check_possibility(N, A, B, C, D); } // Method to check the possibility of making A[] // ascending public static void Check_possibility( int n, long A[], long B[], long C[], long D[]) { // Create a HashMap to store the elements of each // color HashMap<Long, PriorityQueue<Long> > hm = new HashMap<>(); // Add elements of array C to the HashMap for ( int i = 0 ; i < n; i++) { hm.computeIfAbsent(D[i], k -> new PriorityQueue<>()) .add(C[i]); } // Add elements of array A to the HashMap for ( int i = 0 ; i < n; i++) { if (hm.containsKey(B[i])) { hm.get(B[i]).add(A[i]); } } // Flag to check if it's possible to sort array A boolean flag = true ; long prev = - 1 ; // Iterate over array A to sort it for ( int i = 0 ; i < n; i++) { if (!hm.containsKey(B[i])) { if (A[i] < prev) { flag = false ; break ; } else prev = A[i]; } else { PriorityQueue<Long> pq = hm.get(B[i]); while (!pq.isEmpty() && pq.peek() < prev) pq.poll(); if (pq.isEmpty()) { flag = false ; break ; } else prev = pq.poll(); } } // Output the result if (flag) { System.out.println( "YES" ); } else System.out.println( "NO" ); } } |
Python3
import heapq def check_possibility(n, A, B, C, D): # Create a dictionary to store the elements of each color hm = {} # Add elements of array C to the dictionary for i in range (n): hm.setdefault(D[i], []).append(C[i]) heapq.heapify(hm[D[i]]) # Add elements of array A to the dictionary for i in range (n): if B[i] in hm: heapq.heappush(hm[B[i]], A[i]) # Flag to check if it's possible to sort array A flag = True prev = - 1 # Iterate over array A to sort it for i in range (n): if B[i] not in hm: if A[i] < prev: flag = False break else : prev = A[i] else : pq = hm[B[i]] while pq and pq[ 0 ] < prev: heapq.heappop(pq) if not pq: flag = False break else : prev = heapq.heappop(pq) # Output the result if flag: print ( "YES" ) else : print ( "NO" ) # Driver Function def main(): # Input N = 2 A = [ 3 , 2 ] B = [ 1 , 2 ] C = [ 1 , 2 ] D = [ 1 , 1 ] # Function call check_possibility(N, A, B, C, D) # Call the main function main() |
C#
using System; using System.Collections.Generic; class Program { static void CheckPossibility( int n, List< long > A, List< long > B, List< long > C, List< long > D) { Dictionary< long , PriorityQueue< long >> hm = new Dictionary< long , PriorityQueue< long >>(); // Store elements of array C in the dictionary with key as D[i] for ( int i = 0; i < n; i++) { if (!hm.ContainsKey(D[i])) { hm[D[i]] = new PriorityQueue< long >(); } hm[D[i]].Push(C[i]); } // Check if A can be sorted given the conditions in B, C, and D long prev = -1; for ( int i = 0; i < n; i++) { if (!hm.ContainsKey(B[i])) { if (A[i] < prev) { Console.WriteLine( "NO" ); return ; } prev = A[i]; } else { PriorityQueue< long > pq = hm[B[i]]; while (pq.Count > 0 && pq.Top() < prev) { pq.Pop(); } if (pq.Count == 0) { Console.WriteLine( "NO" ); return ; } prev = pq.Top(); pq.Pop(); } } Console.WriteLine( "YES" ); } static void Main() { int N = 2; List< long > A = new List< long > { 3, 2 }; List< long > B = new List< long > { 1, 2 }; List< long > C = new List< long > { 1, 2 }; List< long > D = new List< long > { 1, 1 }; CheckPossibility(N, A, B, C, D); } } // PriorityQueue implementation for C# public class PriorityQueue<T> where T : IComparable<T> { private List<T> heap; public int Count { get { return heap.Count; } } public PriorityQueue() { heap = new List<T>(); } public void Push(T value) { heap.Add(value); int index = heap.Count - 1; while (index > 0) { int parentIndex = (index - 1) / 2; if (heap[index].CompareTo(heap[parentIndex]) >= 0) break ; Swap(index, parentIndex); index = parentIndex; } } public T Pop() { if (heap.Count == 0) throw new InvalidOperationException( "PriorityQueue is empty" ); T top = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); int index = 0; while ( true ) { int leftChildIndex = 2 * index + 1; int rightChildIndex = 2 * index + 2; if (leftChildIndex >= heap.Count) break ; int minIndex = leftChildIndex; if (rightChildIndex < heap.Count && heap[rightChildIndex].CompareTo(heap[leftChildIndex]) < 0) minIndex = rightChildIndex; if (heap[index].CompareTo(heap[minIndex]) <= 0) break ; Swap(index, minIndex); index = minIndex; } return top; } public T Top() { if (heap.Count == 0) throw new InvalidOperationException( "PriorityQueue is empty" ); return heap[0]; } private void Swap( int i, int j) { T temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } } // This code is contributed by shivamgupta310570 |
Javascript
function GFG(N, A, B, C, D) { // Create a Map to store the elements of each color const hm = new Map(); for (let i = 0; i < N; i++) { if (!hm.has(D[i])) { hm.set(D[i], new PriorityQueue()); } hm.get(D[i]).add(C[i]); } // Add elements of array A to the Map for (let i = 0; i < N; i++) { if (hm.has(B[i])) { hm.get(B[i]).add(A[i]); } } // Flag to check if it's possible to sort array A let flag = true ; let prev = -1; // Iterate over array A to sort it for (let i = 0; i < N; i++) { if (!hm.has(B[i])) { if (A[i] < prev) { flag = false ; break ; } else { prev = A[i]; } } else { const pq = hm.get(B[i]); while (!pq.isEmpty() && pq.peek() < prev) { pq.poll(); } if (pq.isEmpty()) { flag = false ; break ; } else { prev = pq.poll(); } } } // Output the result if (flag) { console.log( "YES" ); } else { console.log( "NO" ); } } // PriorityQueue implementation in JavaScript class PriorityQueue { constructor() { this .queue = []; } // Method to add an element to queue add(element) { this .queue.push(element); this .queue.sort((a, b) => a - b); } // Method to get the element at the front of queue peek() { return this .queue.length > 0 ? this .queue[0] : null ; } poll() { return this .queue.shift(); } // Method to check if the queue is empty isEmpty() { return this .queue.length === 0; } } // Driver Code const N = 2; const A = [3, 2]; const B = [1, 2]; const C = [1, 2]; const D = [1, 1]; // Function call GFG(N, A, B, C, D); |
YES
Time Complexity: O(N*logN). This is because for each element in array A, we are performing operations that involve a Priority Queue, which has a time complexity of O(logN) for insertion and deletion.
Auxiliary Space: O(N). This is because a HashMap and Priority Queues to store the elements of the arrays. In the worst case, all elements from arrays A and B could end up in the HashMap, resulting in a space complexity of O(N).