Given an array arr[ ] of N triplets, the task is to order the triplets in descending order. Triplet X will have higher priority than triplet Y if and only if all elements of triplet X will be greater than or equal to the corresponding element of triplet Y. Print Impossible if triplets can’t be ordered.
Examples:
Input: arr = {{1, 2, 3}, {1, 3, 4}, {4, 7, 4}}
Output: {{4, 7, 4}, {1, 3, 4}, {1, 2, 3}}
Explanation:
As it can be seen, all the corresponding elements of triplet C are greater than or equal to triplet B, and all the corresponding elements of triplet B are greater than or equal to triplet A.Input: arr = {{1, 2, 3), {1, 2, 4}, {1, 3, 1}, {10, 20, 30}, {16, 9, 25}}
Output: Impossible
Approach: This problem can be solved using greedy approach. Keep all triplets with their triplet id in different lists and sort these lists of tuple in descending order. Follow the steps below to solve the problem.
- Create three lists of tuples x, y, and z.
- List x, y, z will keep triplets with their triplet id.
- Sort x, on the basis of 1st element of the triplet.
- Sort y, on the basis of the 2nd element of the triplet.
- Sort z, on the basis of 3rd element of the triplet.
- Iterate for i in range [0, N-1], check for all i, if x[i][3] = y[i][3] = z[i][3], then print the respective order, otherwise print ‘Impossible’.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to find any possible ordervector<vector<int>> findOrder(vector<vector<int>> &A, vector<vector<int>> &x, vector<vector<int>> &y, vector<vector<int>> &z){ int flag = 1; // Checking if there is any possible ordering for (int i = 0; i < x.size(); ++i) { if (x[i][3] == y[i][3] && y[i][3] == z[i][3]) continue; else { flag = 0; break; } } vector<vector<int>> Order; if (flag) { for (int i = 0; i < x.size(); ++i) Order.push_back(A[x[i][3]]); } // Return Order return Order;}// Function to print order of triplets if// Any possiblevoid PrintOrder(vector<vector<int>> &A){ // Creating list of paired x, y and z. vector<vector<int>> x, y, z; for (int i = 0; i < A.size(); ++i) { x.push_back({A[i][0], A[i][1], A[i][2], i}); y.push_back({A[i][1], A[i][0], A[i][2], i}); z.push_back({A[i][2], A[i][0], A[i][1], i}); } // Sorting of x, y and z sort(x.rbegin(), x.rend()); sort(y.rbegin(), y.rend()); sort(z.rbegin(), z.rend()); // Function Call vector<vector<int>> order = findOrder(A, x, y, z); // Printing Order if (order.size() == 0) cout << "Impossible"; else { for (auto v : order) { for (auto i : v) cout << i << " "; cout << "\n"; } }}// Driver Codeint main(){ vector<vector<int>> A = {{4, 1, 1}, {3, 1, 1}, {2, 1, 1}}; // Function Call PrintOrder(A); return 0;}// This code is contributed by rakeshsahni |
Python3
# Python program for above approach# Function to find any possible orderdef findOrder(A, x, y, z): flag = 1 # Checking if there is any possible ordering for i in range(len(x)): if x[i][3] == y[i][3] == z[i][3]: continue else: flag = 0 break Order = 'Impossible' if flag: Order = [] for i, j, k, l in x: Order += [A[l]] # Return Order return Order # Function to print order of triplets if# Any possibledef PrintOrder(A): # Creating list of paired x, y and z. x, y, z = [], [], [] for i in range(len(A)): x.append((A[i][0], A[i][1], A[i][2], i)) y.append((A[i][1], A[i][0], A[i][2], i)) z.append((A[i][2], A[i][0], A[i][1], i)) # Sorting of x, y and z x.sort(reverse = True) y.sort(reverse = True) z.sort(reverse = True) # Function Call order = findOrder(A, x, y, z) # Printing Order print(order) # Driver CodeA = [[4, 1, 1], [3, 1, 1], [2, 1, 1]]# Function CallPrintOrder(A) |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static List<List<int>> FindOrder(List<List<int>> A, List<List<int>> x, List<List<int>> y, List<List<int>> z) { int flag = 1; // Checking if there is any possible ordering for (int i = 0; i < x.Count; ++i) { if (x[i][3] == y[i][3] && y[i][3] == z[i][3]) continue; else { flag = 0; break; } } List<List<int>> Order = new List<List<int>>(); if (flag == 1) { for (int i = 0; i < x.Count; ++i) Order.Add(A[x[i][3]]); } // Return Order return Order; } // Function to print order of triplets if // Any possible static void PrintOrder(List<List<int>> A) { // Creating list of paired x, y and z. List<List<int>> x = new List<List<int>>(); List<List<int>> y = new List<List<int>>(); List<List<int>> z = new List<List<int>>(); for (int i = 0; i < A.Count; ++i) { x.Add(new List<int> {A[i][0], A[i][1], A[i][2], i}); y.Add(new List<int> {A[i][1], A[i][0], A[i][2], i}); z.Add(new List<int> {A[i][2], A[i][0], A[i][1], i}); } // Sorting of x, y and z x.Sort((a, b) => b[0].CompareTo(a[0])); y.Sort((a, b) => b[0].CompareTo(a[0])); z.Sort((a, b) => b[0].CompareTo(a[0])); // Function Call List<List<int>> order = FindOrder(A, x, y, z); // Printing Order if (order.Count == 0) Console.WriteLine("Impossible"); else { foreach (var v in order) { Console.WriteLine(string.Join(" ", v)); } } } static void Main(string[] args) { List<List<int>> A = new List<List<int>> { new List<int> {4, 1, 1}, new List<int> {3, 1, 1}, new List<int> {2, 1, 1} }; // Function Call PrintOrder(A); }} |
Javascript
<script> // Javascript program for above approach // Function to find any possible order const findOrder = (A, x, y, z) => { let flag = 1; // Checking if there is any possible ordering for (let i = 0; i < x.length; ++i) { let index_x = JSON.stringify(x[i]); let index_y = JSON.stringify(y[i]); let index_z = JSON.stringify(z[i]); // index_x = [[4,1,1,0]] as string // we have to find 0 mean index_x[8] if (index_x[8] == index_y[8] && index_y[8] == index_z[8]) continue; else { flag = 0; break; } } let Order = []; if (flag) { for (let itm in x) { let index_x = JSON.stringify(x[itm]); Order.push(A[index_x[8] - '0']); } } // Return Order return Order; } // Function to print order of triplets if // Any possible const PrintOrder = (A) => { // Creating list of paired x, y and z. let x = []; let y = []; let z = []; for (let i = 0; i < A.length; ++i) { x.push([[A[i][0], A[i][1], A[i][2], i]]); y.push([[A[i][1], A[i][0], A[i][2], i]]); z.push([[A[i][2], A[i][0], A[i][1], i]]); } // Sorting of x, y and z x.sort((a, b) => a - b) y.sort((a, b) => a - b) z.sort((a, b) => a - b) // Function Call let order = findOrder(A, x, y, z); // Printing Order if (order.length === 0) document.write("Impossible"); else document.write(order); } // Driver Code const A = [[4, 1, 1], [3, 1, 1], [2, 1, 1]]; // Function Call PrintOrder(A);// This code is contributed by rakeshsahni</script> |
Java
import java.util.*;public class Main { // Function to find any possible order public static List<List<Integer>> findOrder(List<List<Integer>> A, List<List<Integer>> x, List<List<Integer>> y, List<List<Integer>> z) { int flag = 1; // Checking if there is any possible ordering for (int i = 0; i < x.size(); ++i) { if (x.get(i).get(3).equals(y.get(i).get(3)) && y.get(i).get(3).equals(z.get(i).get(3))) { continue; } else { flag = 0; break; } } List<List<Integer>> Order = new ArrayList<>(); if (flag == 1) { for (int i = 0; i < x.size(); ++i) { Order.add(A.get(x.get(i).get(3))); } } // Return Order return Order; } // Function to print order of triplets if // Any possible public static void printOrder(List<List<Integer>> A) { // Creating list of paired x, y and z. List<List<Integer>> x = new ArrayList<>(); List<List<Integer>> y = new ArrayList<>(); List<List<Integer>> z = new ArrayList<>(); for (int i = 0; i < A.size(); ++i) { x.add(Arrays.asList(A.get(i).get(0), A.get(i).get(1), A.get(i).get(2), i)); y.add(Arrays.asList(A.get(i).get(1), A.get(i).get(0), A.get(i).get(2), i)); z.add(Arrays.asList(A.get(i).get(2), A.get(i).get(0), A.get(i).get(1), i)); } // Sorting of x, y and z Comparator<List<Integer>> comp = new Comparator<List<Integer>>() { @Override public int compare(List<Integer> a, List<Integer> b) { return b.get(0).compareTo(a.get(0)); } }; Collections.sort(x, comp); Collections.sort(y, comp); Collections.sort(z, comp); // Function Call List<List<Integer>> order = findOrder(A, x, y, z); // Printing Order if (order.size() == 0) { System.out.println("Impossible"); } else { for (List<Integer> v : order) { for (int i : v) { System.out.print(i + " "); } System.out.println(); } } } // Driver Code public static void main(String[] args) { List<List<Integer>> A = new ArrayList<>(); A.add(Arrays.asList(4, 1, 1)); A.add(Arrays.asList(3, 1, 1)); A.add(Arrays.asList(2, 1, 1)); // Function Call printOrder(A); }} |
Output:
[[4, 1, 1], [3, 1, 1], [2, 1, 1]]
Time Complexity: O(NlogN)
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!