Rearrange List to Follow Given Operators Sequence

Given a list of n integers and consider another list which has n-1 “<” or “>” operators. Your task is to form a valid sequence by rearranging the initial list such that it follows the operator’s sequence in the final list. “vector” is a list containing integers “operators” is a list containing operators constraints: 2<=n<=1000.

Examples:

Input :
vector = [4, 2, 3, 1, 5] 
operators = ['>', '<', '<', '>']
Output :[5, 1, 2, 4, 3]
Explanation : since (5 > 1 < 2 < 4 > 3)

Input :
vector = [8, 7, 6, 5, 2, 1, 4] 
operators = ['<', '>', '<', '<', '>', '>']
Output :[1, 8, 2, 4, 7, 6, 5]
Explanation : since (1 < 8 > 2 < 4 < 7 > 6 > 5)

Approach:

This problem can be solved using Two Pointer Approach:
1. Sort the given vector list in ascending order
2. Take two pointers pointing to extreme ends of the vector list say i and j.
3. For the given operator in operator list:

(i). If operator is < consider element at vector[i] and move i towards right
(ii). If operator is > consider element at vector[j] and move j towards left 4. repeat the process till i and j are crossed.

Implementation:

# A Two Pointer based program to organize the vector elements 
# so that it follows the operator sequence.
# OrganizeInOrder is the function that does the task

def OrganizeInOrder(vec, op, n):
    # result is a list which stores resultant values
    result = [0] * n
    
    # sorting vector in ascending order
    vec.sort()
    
    # define two pointers as i and j
    i, j = 0, n-1
    
    # k is used to track operators
    k = 0
    
    # Condition to halt the loop
    # 1. when i and j are crossed
    # 2. when k value less than n-2 
    # (since there are n-1 elements and index start from 0)
    
    while(i <= j and k <= n - 2):
        # when the operator is " &lt; " consider element at ith index
        if(op[k] == '<'):
            result[k] = vec[i]
            i += 1
        # when the operator is " &gt; " consider element at jth index
        else:
            result[k] = vec[j]
            j -= 1
        # increment k so that we consider next operator in list
        k += 1
    result[n-1] = vec[i]
    return result

vector = [4, 2, 3, 1, 5]
operators = ['>','<','<','>']
print(OrganizeInOrder(vector, operators, len(vector)))

Output:

[5, 1, 2, 4, 3]

Time complexity: O(nlogn).

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.