LeetCode : 942. DI String Match

[congr]

https://leetcode.com/problems/di-string-match/

[congr]

Slow - O(NLogN)

class Solution {
    public int[] diStringMatch(String S) {
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());

        for (int i = 0; i <= S.length(); i++) {
            minHeap.add(i);
            maxHeap.add(i);
        }

        int[] res = new int[S.length()+1];
        int i = 0;
        for (char c : S.toCharArray()) {
            if (c == 'I') {
                res[i] = minHeap.remove();
                maxHeap.remove(res[i]);
                i++;
            } else if (c == 'D') {
                res[i] = maxHeap.remove();
                minHeap.remove(res[i]);
                i++;
            }
        }

        res[i] = minHeap.isEmpty() ? maxHeap.remove() : minHeap.remove(); 
        return res;
    }
}

[congr]

O(N)

Runtime: 5 ms, faster than 100.00% of Java online submissions for DI String Match. Memory Usage: 22.8 MB, less than 96.90% of Java online submissions for DI String Match.

class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int[] res = new int[N+1];

        int left = 0, right = N;
        int i = 0;
        for (char c : S.toCharArray()) {
            if (c == 'I') res[i++] = left++;
            else if (c == 'D') res[i++] = right--;
        }

        res[i] = right; // or left (left = right)

        return res;
    }
}