🚀 Amazon Online Assessment | Lexicographically Largest Array (LeetCode / HackerRank)

Round 1

Questions: You are given an array arr of size n containing positive integers and a binary string state of length n. The state[i] = '1' indicates that the element at index i is initially available for selection, while state[i] = '0' means it is locked.

You need to select exactly m elements from the array. The selection process follows these rules:

• At each step, select the largest available element (if multiple elements have the same value, select the one with the highest index).
• After selecting an element from index i, unlock its adjacent locked elements (i-1 and i+1) if they exist.
• The process continues until m elements are selected.

The output should be the lexicographically largest sequence of selected elements.

Function Signature:

public static List<Integer> generateNewArray(List<Integer> arr, String state, int m){
}

Example 1 Input:

arr = [10, 5, 7, 6];
state = "0101";
m = 2;

Output:

[6, 7]

Explanation: Initially available elements: {6} (from state[3] = '1'). Select 6, unlocking state[2] → {6} → {7}. Select 7. We have selected m = 2 elements.

Example 2 Input:

arr = [4, 9, 1, 2, 10];
state = "10010";
m = 4;

Output:

[4, 9, 10, 10]

Explanation: Initially available: {4, 10}. Select 4, unlocking state[1] → {4} → {9}. Select 9, unlocking state[2] → {9} → {1}. Select 10, unlocking state[3] → {10} → {2}. Select 10 again.

Candidate's Approach

Use a max-heap (priority queue) to always pick the largest available element.

• Store elements in the form (value, index) in the heap.
• Process m selections:
  • Extract the largest available element.
  • Unlock adjacent locked elements and add them to the heap.
  • Reinsert the selected element since it can be picked again.

Time Complexity:

• Heap operations: O(log n).
• Total operations: O(m log n), which is efficient for n ≤ 10^5.

Interviewer's Feedback

No feedback provided.

---