Problem

The sequence [0, 1, ..., N] has been jumbled, and the only clue you have for its order is an array representing whether each number is larger or smaller than the last. Given this information, reconstruct an array that is consistent with it.

Examples

Example 1

1
2
3

Input: [None, +, +, -, +]
Output: [1, 2, 3, 0, 4]
Explanation: Starting with any valid number, we follow the pattern: increase, increase, decrease, increase to get a valid sequence.

Example 2

1
2
3

Input: [None, -, +, -, -]
Output: [4, 0, 1, 2, 3]
Explanation: We start high and follow the pattern: decrease, increase, decrease, decrease.

Example 3

1
2
3

Input: [None, +, -, +]
Output: [0, 2, 1, 3]
Explanation: Following the pattern: increase, decrease, increase gives us a valid reconstruction.

Example 4

1
2
3

Input: [None, -, -, -]
Output: [3, 2, 1, 0]
Explanation: Continuous decrease pattern from maximum to minimum.

Solution

Method 1 - Greedy Construction

Intuition

We can solve this greedily by maintaining available numbers and choosing the appropriate next number based on the comparison operator. When we see a ‘+’, we want to pick the smallest available number that’s larger than current. When we see a ‘-’, we want to pick the largest available number that’s smaller than current.

Approach

  1. Initialize a set or list of available numbers from 0 to N
  2. Start with any valid number (we can choose the middle value for balance)
  3. For each comparison operator in the clues array:
    • If ‘+’: find the smallest available number greater than current
    • If ‘-’: find the largest available number smaller than current
    • Remove the chosen number from available set
    • Add it to result
  4. Return the reconstructed sequence

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    vector<int> reconstructSequence(vector<string>& clues) {
        int n = clues.size();
        vector<int> ans;
        set<int> available;
        
        for (int i = 0; i < n; i++) {
            available.insert(i);
        }
        
        int curr = n / 2;
        ans.push_back(curr);
        available.erase(curr);
        
        for (int i = 1; i < n; i++) {
            if (clues[i] == "+") {
                auto it = available.upper_bound(curr);
                curr = *it;
            } else {
                auto it = available.lower_bound(curr);
                --it;
                curr = *it;
            }
            ans.push_back(curr);
            available.erase(curr);
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func reconstructSequence(clues []string) []int {
    n := len(clues)
    ans := make([]int, 0, n)
    available := make(map[int]bool)
    
    for i := 0; i < n; i++ {
        available[i] = true
    }
    
    curr := n / 2
    ans = append(ans, curr)
    delete(available, curr)
    
    for i := 1; i < n; i++ {
        if clues[i] == "+" {
            for j := curr + 1; j < n; j++ {
                if available[j] {
                    curr = j
                    break
                }
            }
        } else {
            for j := curr - 1; j >= 0; j-- {
                if available[j] {
                    curr = j
                    break
                }
            }
        }
        ans = append(ans, curr)
        delete(available, curr)
    }
    
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int[] reconstructSequence(String[] clues) {
        int n = clues.length;
        int[] ans = new int[n];
        TreeSet<Integer> available = new TreeSet<>();
        
        for (int i = 0; i < n; i++) {
            available.add(i);
        }
        
        int curr = n / 2;
        ans[0] = curr;
        available.remove(curr);
        
        for (int i = 1; i < n; i++) {
            if (clues[i].equals("+")) {
                curr = available.higher(curr);
            } else {
                curr = available.lower(curr);
            }
            ans[i] = curr;
            available.remove(curr);
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun reconstructSequence(clues: Array<String>): IntArray {
        val n = clues.size
        val ans = IntArray(n)
        val available = sortedSetOf<Int>()
        
        for (i in 0 until n) {
            available.add(i)
        }
        
        var curr = n / 2
        ans[0] = curr
        available.remove(curr)
        
        for (i in 1 until n) {
            curr = if (clues[i] == "+") {
                available.tailSet(curr + 1).first()
            } else {
                available.headSet(curr).last()
            }
            ans[i] = curr
            available.remove(curr)
        }
        
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def reconstructSequence(self, clues: List[str]) -> List[int]:
        n = len(clues)
        ans = []
        available = set(range(n))
        
        curr = n // 2
        ans.append(curr)
        available.remove(curr)
        
        for i in range(1, n):
            if clues[i] == "+":
                curr = min(x for x in available if x > curr)
            else:
                curr = max(x for x in available if x < curr)
            ans.append(curr)
            available.remove(curr)
        
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn reconstruct_sequence(clues: Vec<String>) -> Vec<i32> {
        let n = clues.len();
        let mut ans = Vec::with_capacity(n);
        let mut available: std::collections::BTreeSet<i32> = (0..n as i32).collect();
        
        let curr = n as i32 / 2;
        ans.push(curr);
        available.remove(&curr);
        
        let mut curr = curr;
        for i in 1..n {
            if clues[i] == "+" {
                curr = *available.range((curr + 1)..).next().unwrap();
            } else {
                curr = *available.range(..curr).next_back().unwrap();
            }
            ans.push(curr);
            available.remove(&curr);
        }
        
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    reconstructSequence(clues: string[]): number[] {
        const n = clues.length;
        const ans: number[] = [];
        const available = new Set<number>();
        
        for (let i = 0; i < n; i++) {
            available.add(i);
        }
        
        let curr = Math.floor(n / 2);
        ans.push(curr);
        available.delete(curr);
        
        for (let i = 1; i < n; i++) {
            if (clues[i] === "+") {
                curr = Math.min(...Array.from(available).filter(x => x > curr));
            } else {
                curr = Math.max(...Array.from(available).filter(x => x < curr));
            }
            ans.push(curr);
            available.delete(curr);
        }
        
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n²) in the worst case for finding the next valid number, where n is the length of the sequence
  • 🧺 Space complexity: O(n) for storing the available numbers and result array

Method 2 - Stack-Based Construction

Intuition

We can use a more sophisticated approach by treating this as placing numbers optimally. We can use stacks to handle increasing and decreasing subsequences, which allows us to construct the sequence more efficiently.

Approach

  1. Scan the clues array to identify consecutive ‘+’ and ‘-’ segments
  2. For each segment, we know we need either an increasing or decreasing subsequence
  3. Use two stacks or direct assignment to place numbers optimally
  4. For ‘+’ segments, assign consecutive increasing numbers
  5. For ‘-’ segments, assign consecutive decreasing numbers
  6. Ensure smooth transitions between segments

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<int> reconstructSequenceOptimal(vector<string>& clues) {
        int n = clues.size();
        vector<int> ans(n);
        int low = 0, high = n - 1;
        
        int i = 1;
        while (i < n) {
            if (clues[i] == "+") {
                ans[i - 1] = low++;
                while (i < n && clues[i] == "+") {
                    ans[i] = low++;
                    i++;
                }
            } else {
                int start = i - 1;
                while (i < n && clues[i] == "-") {
                    i++;
                }
                for (int j = start; j < i; j++) {
                    ans[j] = high--;
                }
            }
        }
        
        if (ans[n - 1] == 0) {
            ans[n - 1] = (ans[n - 2] == low) ? high : low;
        }
        
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func reconstructSequenceOptimal(clues []string) []int {
    n := len(clues)
    ans := make([]int, n)
    low, high := 0, n-1
    
    i := 1
    for i < n {
        if clues[i] == "+" {
            ans[i-1] = low
            low++
            for i < n && clues[i] == "+" {
                ans[i] = low
                low++
                i++
            }
        } else {
            start := i - 1
            for i < n && clues[i] == "-" {
                i++
            }
            for j := start; j < i; j++ {
                ans[j] = high
                high--
            }
        }
    }
    
    if ans[n-1] == 0 {
        if ans[n-2] == low {
            ans[n-1] = high
        } else {
            ans[n-1] = low
        }
    }
    
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public int[] reconstructSequenceOptimal(String[] clues) {
        int n = clues.length;
        int[] ans = new int[n];
        int low = 0, high = n - 1;
        
        int i = 1;
        while (i < n) {
            if (clues[i].equals("+")) {
                ans[i - 1] = low++;
                while (i < n && clues[i].equals("+")) {
                    ans[i] = low++;
                    i++;
                }
            } else {
                int start = i - 1;
                while (i < n && clues[i].equals("-")) {
                    i++;
                }
                for (int j = start; j < i; j++) {
                    ans[j] = high--;
                }
            }
        }
        
        if (ans[n - 1] == 0) {
            ans[n - 1] = (ans[n - 2] == low) ? high : low;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    fun reconstructSequenceOptimal(clues: Array<String>): IntArray {
        val n = clues.size
        val ans = IntArray(n)
        var low = 0
        var high = n - 1
        
        var i = 1
        while (i < n) {
            if (clues[i] == "+") {
                ans[i - 1] = low++
                while (i < n && clues[i] == "+") {
                    ans[i] = low++
                    i++
                }
            } else {
                val start = i - 1
                while (i < n && clues[i] == "-") {
                    i++
                }
                for (j in start until i) {
                    ans[j] = high--
                }
            }
        }
        
        if (ans[n - 1] == 0) {
            ans[n - 1] = if (ans[n - 2] == low) high else low
        }
        
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def reconstructSequenceOptimal(self, clues: List[str]) -> List[int]:
        n = len(clues)
        ans = [0] * n
        low, high = 0, n - 1
        
        i = 1
        while i < n:
            if clues[i] == "+":
                ans[i - 1] = low
                low += 1
                while i < n and clues[i] == "+":
                    ans[i] = low
                    low += 1
                    i += 1
            else:
                start = i - 1
                while i < n and clues[i] == "-":
                    i += 1
                for j in range(start, i):
                    ans[j] = high
                    high -= 1
        
        if ans[n - 1] == 0:
            ans[n - 1] = high if ans[n - 2] == low else low
        
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

impl Solution {
    pub fn reconstruct_sequence_optimal(clues: Vec<String>) -> Vec<i32> {
        let n = clues.len();
        let mut ans = vec![0; n];
        let mut low = 0;
        let mut high = (n - 1) as i32;
        
        let mut i = 1;
        while i < n {
            if clues[i] == "+" {
                ans[i - 1] = low;
                low += 1;
                while i < n && clues[i] == "+" {
                    ans[i] = low;
                    low += 1;
                    i += 1;
                }
            } else {
                let start = i - 1;
                while i < n && clues[i] == "-" {
                    i += 1;
                }
                for j in start..i {
                    ans[j] = high;
                    high -= 1;
                }
            }
        }
        
        if ans[n - 1] == 0 {
            ans[n - 1] = if ans[n - 2] == low { high } else { low };
        }
        
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    reconstructSequenceOptimal(clues: string[]): number[] {
        const n = clues.length;
        const ans: number[] = new Array(n).fill(0);
        let low = 0, high = n - 1;
        
        let i = 1;
        while (i < n) {
            if (clues[i] === "+") {
                ans[i - 1] = low++;
                while (i < n && clues[i] === "+") {
                    ans[i] = low++;
                    i++;
                }
            } else {
                const start = i - 1;
                while (i < n && clues[i] === "-") {
                    i++;
                }
                for (let j = start; j < i; j++) {
                    ans[j] = high--;
                }
            }
        }
        
        if (ans[n - 1] === 0) {
            ans[n - 1] = (ans[n - 2] === low) ? high : low;
        }
        
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the sequence, as we process each element once
  • 🧺 Space complexity: O(1) excluding the output array, as we only use a constant amount of extra space