Given two arrays, array A[] of size N and array B[] of size N-1, array A has all the positive elements and -1 for the empty values and array B has 3 characters {‘>’, ‘=’, ‘<‘} which indicates the following:
- ‘>‘ means A[i] > A[i+1]
- ‘=‘ means A[i] = A[i+1]
- ‘<‘ means A[i] < A[i+1]
The task is to find if we can fill -1(empty values) of A with some positive values that also satisfy the relations between the adjacents mentioned in array B.
Examples:
Input: N = 6, A = {8, 6, -1, -1, -1, 11}, B = {‘>’, ‘>’, ‘=’, ‘<‘, ‘>’}
Output: Yes
Explanation: Consider, A becomes {8, 6, 5, 5, 12, 11},
It satisfies B, so the answer will be ‘Yes’.Input: N = 5, A = {4, 1, -1, -1, 7}, B = {‘<‘, ‘<‘, ‘<‘, ‘<‘}
Output: No
Approach: The problem can be solved based on the following mathematical idea:
Use range to compare whether we can have a valid solution for a particular index and change the range accordingly.
Initially, the left range is 0 and the right range is INT_MAX.
- If ‘<‘ operator is encountered, then the valid range for A[i+1] is left = A[i]+1 and right = INT_MAX.
- If ‘>’ operator is encountered, then the valid range for A[i+1] is left = 0 and right = A[i] – 1.
- If ‘=’ operator is encountered, then the valid range for A[i+1] is left = A[i] and right = A[i]
- Values of ranges are changed when A[i] is given, but when A[i] = -1 ranges are compared and changed according to the above-mentioned conditions
- If left ? right and left ? 0 and right ? 0 is satisfied for each index position, then ‘Yes’ is returned, otherwise ‘No’ is returned.
Below is the implementation of the above approach.
C++
// C++ code for this approach#include <bits/stdc++.h>using namespace std;// Function to check whether array A// can be made such that all operator// of array B holds true for each index istring checkComparisons(int N, vector<int> A, vector<char> B){ // Declaring initial ranges as 0 to Infinity int left = 0, right = INT_MAX, index = 0; bool valid = 1; for (int i = 0; i < N - 1; i++, index++) { // If current element is not empty if (A[i] != -1) { // Compare normal elements // (non empty i.e. != -1) based on B if (A[i + 1] != -1) { if (B[index] == '>') { if (A[i] <= A[i + 1]) return "No"; } if (B[index] == '=') { if (A[i] != A[i + 1]) return "No"; } if (B[index] == '<') { if (A[i] >= A[i + 1]) return "No"; } } // Compare and update ranges // for empty spaces else { if (B[index] == '>') { left = 0; right = A[i] - 1; } if (B[index] == '=') { left = A[i]; right = A[i]; } if (B[index] == '<') { left = A[i] + 1; right = INT_MAX; } } } // If current element is empty else { // Compare and update ranges if // next element is not empty if (A[i + 1] != -1) { if (B[index] == '>') { if (right <= A[i + 1]) return "No"; } if (B[index] == '=') { if ((left > A[i + 1]) || (right < A[i + 1])) return "No"; } if (B[index] == '<') { if (left >= A[i + 1]) return "No"; } } // Compare and update ranges if // next element is empty based on // previous ranges else { if (B[index] == '>') { left = 0; right--; } if (B[index] == '<') { left++; right = INT_MAX; } } } if (left > right) return "No"; if (right < 0) return "No"; if (left < 0) return "No"; } return "Yes";}// Driver Codeint main(){ int N = 6; vector<int> A{ 8, 6, -1, -1, -1, 11 }; vector<char> B{ '>', '>', '=', '<', '>' }; // Function call cout << checkComparisons(N, A, B); return 0;} |
Java
// Java code for this approachimport java.io.*;class GFG { // Function to check whether array A // can be made such that all operator // of array B holds true for each index i public static String checkComparisons(int N, int A[], char B[]) { // Declaring initial ranges as 0 to Infinity int left = 0, right = Integer.MAX_VALUE, index = 0; boolean valid = true; for (int i = 0; i < N - 1; i++, index++) { // If current element is not empty if (A[i] != -1) { // Compare normal elements // (non empty i.e. != -1) based on B if (A[i + 1] != -1) { if (B[index] == '>') { if (A[i] <= A[i + 1]) return "No"; } if (B[index] == '=') { if (A[i] != A[i + 1]) return "No"; } if (B[index] == '<') { if (A[i] >= A[i + 1]) return "No"; } } // Compare and update ranges // for empty spaces else { if (B[index] == '>') { left = 0; right = A[i] - 1; } if (B[index] == '=') { left = A[i]; right = A[i]; } if (B[index] == '<') { left = A[i] + 1; right = Integer.MAX_VALUE; } } } // If current element is empty else { // Compare and update ranges if // next element is not empty if (A[i + 1] != -1) { if (B[index] == '>') { if (right <= A[i + 1]) return "No"; } if (B[index] == '=') { if ((left > A[i + 1]) || (right < A[i + 1])) return "No"; } if (B[index] == '<') { if (left >= A[i + 1]) return "No"; } } // Compare and update ranges if // next element is empty based on // previous ranges else { if (B[index] == '>') { left = 0; right--; } if (B[index] == '<') { left++; right = Integer.MAX_VALUE; } } } if (left > right) return "No"; if (right < 0) return "No"; if (left < 0) return "No"; } return "Yes"; } // Driver Code public static void main(String[] args) { int N = 6; int A[] = { 8, 6, -1, -1, -1, 11 }; char B[] = { '>', '>', '=', '<', '>' }; // Function call System.out.print(checkComparisons(N, A, B)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code for this approach# Function to check whether array A# can be made such that all operator# of array B holds true for each index iimport sysdef checkComparisons(N, A, B): # Declaring initial ranges as 0 to Infinity left = 0 right = -sys.maxsize-1 index = 0; valid = 1; for i in range (N-1): i = i + 1 index = index + 1 # If current element is not empty if (A[i] != -1): # Compare normal elements # (non empty i.e. != -1) based on B if (A[i + 1] != -1): if (B[index] == '>'): if (A[i] <= A[i + 1]): return "No" if (B[index] == '='): if (A[i] != A[i + 1]): return "No" if (B[index] == '<'): if (A[i] >= A[i + 1]): return "No" # Compare and update ranges # for empty spaces else: if (B[index] == '>'): left = 0 right = A[i] - 1 if (B[index] == '='): left = A[i] right = A[i] if (B[index] == '<'): left = A[i] + 1 right = -sys.maxsize - 1 # If current element is empty else: # Compare and update ranges if # next element is not empty if (A[i + 1] != -1): if (B[index] == '>'): if (right <= A[i + 1]): return "No" if (B[index] == '='): if ((left > A[i + 1]) or (right < A[i + 1])): return "No" if (B[index] == '<'): if (left >= A[i + 1]): return "No" # Compare and update ranges if # next element is empty based on # previous ranges else: if (B[index] == '>'): left = 0 right=right-1 if (B[index] == '<'): left=left+1 right = -sys.maxsize-1 if (left > right): return "No" if (right < 0): return "No" if (left < 0): return "No" return "Yes" # Driver CodeN = 6A = [8, 6, -1, -1, -1, 11]B = [ '>', '>', '=', '<', '>' ]# Function callprint(checkComparisons(N, A, B))# This code is contributed by Atul_kumar_Shrivastava |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG { // Function to check whether array A // can be made such that all operator // of array B holds true for each index i public static String checkComparisons(int N, int[] A, char[] B) { // Declaring initial ranges as 0 to Infinity int left = 0, right = Int32.MaxValue, index = 0; bool valid = true; for (int i = 0; i < N - 1; i++, index++) { // If current element is not empty if (A[i] != -1) { // Compare normal elements // (non empty i.e. != -1) based on B if (A[i + 1] != -1) { if (B[index] == '>') { if (A[i] <= A[i + 1]) return "No"; } if (B[index] == '=') { if (A[i] != A[i + 1]) return "No"; } if (B[index] == '<') { if (A[i] >= A[i + 1]) return "No"; } } // Compare and update ranges // for empty spaces else { if (B[index] == '>') { left = 0; right = A[i] - 1; } if (B[index] == '=') { left = A[i]; right = A[i]; } if (B[index] == '<') { left = A[i] + 1; right = Int32.MaxValue; } } } // If current element is empty else { // Compare and update ranges if // next element is not empty if (A[i + 1] != -1) { if (B[index] == '>') { if (right <= A[i + 1]) return "No"; } if (B[index] == '=') { if ((left > A[i + 1]) || (right < A[i + 1])) return "No"; } if (B[index] == '<') { if (left >= A[i + 1]) return "No"; } } // Compare and update ranges if // next element is empty based on // previous ranges else { if (B[index] == '>') { left = 0; right--; } if (B[index] == '<') { left++; right = Int32.MaxValue; } } } if (left > right) return "No"; if (right < 0) return "No"; if (left < 0) return "No"; } return "Yes"; } // Driver Code public static void Main() { int N = 6; int[] A = { 8, 6, -1, -1, -1, 11 }; char[] B = { '>', '>', '=', '<', '>' }; // Function call Console.WriteLine(checkComparisons(N, A, B)); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for this approach const INT_MAX = 2147483647; // Function to check whether array A // can be made such that all operator // of array B holds true for each index i const checkComparisons = (N, A, B) => { // Declaring initial ranges as 0 to Infinity let left = 0, right = INT_MAX, index = 0; let valid = 1; for (let i = 0; i < N - 1; i++, index++) { // If current element is not empty if (A[i] != -1) { // Compare normal elements // (non empty i.e. != -1) based on B if (A[i + 1] != -1) { if (B[index] == '>') { if (A[i] <= A[i + 1]) return "No"; } if (B[index] == '=') { if (A[i] != A[i + 1]) return "No"; } if (B[index] == '<') { if (A[i] >= A[i + 1]) return "No"; } } // Compare and update ranges // for empty spaces else { if (B[index] == '>') { left = 0; right = A[i] - 1; } if (B[index] == '=') { left = A[i]; right = A[i]; } if (B[index] == '<') { left = A[i] + 1; right = INT_MAX; } } } // If current element is empty else { // Compare and update ranges if // next element is not empty if (A[i + 1] != -1) { if (B[index] == '>') { if (right <= A[i + 1]) return "No"; } if (B[index] == '=') { if ((left > A[i + 1]) || (right < A[i + 1])) return "No"; } if (B[index] == '<') { if (left >= A[i + 1]) return "No"; } } // Compare and update ranges if // next element is empty based on // previous ranges else { if (B[index] == '>') { left = 0; right--; } if (B[index] == '<') { left++; right = INT_MAX; } } } if (left > right) return "No"; if (right < 0) return "No"; if (left < 0) return "No"; } return "Yes"; } // Driver Code let N = 6; let A = [8, 6, -1, -1, -1, 11]; let B = ['>', '>', '=', '<', '>']; // Function call document.write(checkComparisons(N, A, B)); // This code is contributed by rakeshsahni</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
