Check if empty spaces of Array can be filled maintaining given relations of adjacent

0 0 9 minutes read

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 i
string 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 Code
int 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 approach
import 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 i
import sys
def 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 Code
N = 6
A = [8, 6, -1, -1, -1, 11]
B = [ '>', '>', '=', '<', '>' ]
 
# Function call
print(checkComparisons(N, A, B))
 
# This code is contributed by Atul_kumar_Shrivastava

C#

// C# implementation of above approach
using 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 zambiatek!