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)
Recommended: Printing special pattern in Python
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 " < " 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)))
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.