Java O(n) time,O(n) space AC solution 14ms like count sort


  • 9
    J

    The basic idea is to count how many numbers are smaller(self include) than the current number.
    We then compare this count to the org.
    It is pretty like the idea of count sort.

    public class Solution {
        public boolean sequenceReconstruction(int[] org, int[][] seqs) {
            int len = org.length;
            int[] map = new int[len + 1];//map number to its index
            Arrays.fill(map, -1);
            int[] memo = new int[org.length];//count how many numbers are smaller(on the right)
            for (int i = 0; i < len; i++) {
                map[org[i]] = i;
            }
            for (int[] seq : seqs) {
                if (seq.length == 0) continue;
                int prev = seq[0];
                if (prev <= 0 || prev > len || map[prev] == -1) return false;
                for (int i = 1; i < seq.length; i++) {
                    int curr = seq[i];
                    if (curr <= 0 || curr > len || map[curr] == -1) return false;
                    memo[map[prev]] = Math.max(memo[map[prev]], len - map[curr] + 1);
                    prev = curr;
                }
                memo[map[prev]] = Math.max(memo[map[prev]], 1);
            }
            for (int i = 0; i < memo.length; i++) {
                if (memo[i] != len - i) return false;
            }
            return true;
        }
    }
    

  • 0
    L

    What an inspiring solution! I figure out my similar solution based on your great idea. My idea is to store the closest (actually consecutive) previous element for each. Then finally, we should end up with n distinct elements from zero to n, which means the last element is void. If someone can improve my final check, it would be better. (Sorting would be alright but we can definitely do it with linear time).

    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
            if (seqs.length == 0) {
                return false;
            }
            // store order in org
            Map<Integer, Integer> order = new HashMap<>();
            for (int i = 0 ; i < org.length; i ++) {
                order.put(org[i], i);
            }
            // store the closest prev element for each
            int[] prev = new int[org.length + 1];
            for (int i = 0 ; i < seqs.length ; i ++) {
                if (seqs[i].length == 0) continue;
                if (seqs[i][0] <= 0 || seqs[i][0] > org.length) return false;
                for (int j = 1 ; j < seqs[i].length ; j ++) {
                    if (seqs[i][j] <= 0 || seqs[i][j] > org.length) return false;
                    if (order.get(seqs[i][j]) <= order.get(seqs[i][j - 1])) return false;
                    if (prev[seqs[i][j]] == 0) {
                        prev[seqs[i][j]] = seqs[i][j - 1];
                    } else {
                        if (order.get(seqs[i][j]) <= order.get(prev[seqs[i][j]])) {
                            return false;
                        }
                        prev[seqs[i][j]] = org[Math.max(order.get(seqs[i][j - 1]), order.get(prev[seqs[i][j]]))];
                    }
                }
            }
            // prev should miss the only leaf and resulting with n - 1 elments from zero to n
            boolean[] test = new boolean[org.length + 1];
            for (int i = 1 ; i < prev.length ; i ++) {
                test[prev[i]] = true;
            }
            int count = 0;
            for (int i = 1 ; i < test.length ; i ++) {
                if (!test[i]) {
                    count ++;
                }
            }
            return count == 1;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.