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)
This problem can be solved using TWO POINTERS APPROACH
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 " < " consider element at ith index
if(op[k] == '<'):
result[k] = vec[i]
i += 1
# when the operator is " > " 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)))