Greedy - java O(n) time O(n) space solution without using map


  • 0
    Y
    public class Solution {
        public boolean isPossible(int[] nums) {
             //  count appearance of each number
            List<int[]> list = new ArrayList<>();
            list.add(new int[]{nums[0], 1});
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == nums[i-1]) {
                    list.get(list.size()-1)[1]++;
                } else {
                    list.add(new int[]{nums[i],1});
                }
            }
            int i = 0;
            while(true) {
                // skip num with 0 appearance
                while (i < list.size() && list.get(i)[1] == 0) i++;
                // reach the end, break
                if (i == list.size()) break; 
                // remain fewer than 3 unique number, return false
                if (list.size()-i < 3) return false;
                int d = 1, c = list.get(i)[1]; 
                list.get(i)[1] = 0;
                // at least 3 consecutive number required
                for (; d < 3; d++) {
                    int[]cur = list.get(i+d); 
                    int exp = list.get(i)[0]+d; 
                    if (cur[0] != exp || cur[1] < c) return false;
                    cur[1] -= c;
                }
                // check whether we need extend to more than 3 numbers
                for (; i+d < list.size(); d++) {
                    int[] cur = list.get(i+d); 
                    int[] pre = list.get(i+d-1); 
                    int exp = list.get(i)[0]+d; 
                    if (cur[0] != exp || cur[1] <= pre[1]) break;
                    c = Math.min(c, cur[1]-pre[1]); 
                    cur[1] -= c;
                }
            }
            return true;
        }
    

  • 0
    F

    @yellowstar1986 Hello,Could you please tell me why cur[1] <= pre[1] need break, when cur frequency is equal to pre frequency, why cur can't be attached to previous lists? Also, I'm confused about c = Math.min(c, cur[1]-pre[1]);, could give me some example why you think in this way? Thank you!


Log in to reply
 

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