Java O(n) Time and space


  • 0
    V

    Each number can be part of a list or it can start its own list. For number n(occurs x times) and n + 1 (occurs y times) if y > x then (y - x) occurrences of (n + 1) have to start their own list. For each of the next number if we try to add it to pre-existing lists in reverse order(since this way we will encounter shorter lists first) we will only create new lists when we have to.

    Once we have all the lists we can verify if any list is of size < 3 and return false else return true.

    public class Solution {
        public boolean isPossible(int[] nums) {
            if(nums.length < 3) return false;
            List<Integer> countOfNums = new ArrayList<>();
            List<Integer> uniqueNums = new ArrayList<>();
            int count = 0;
            for(int i = 0 ; i < nums.length ; ++i) {
                if(i == nums.length - 1 || nums[i + 1] != nums[i]) {
                    countOfNums.add(count + 1);
                    uniqueNums.add(nums[i]);
                    count = 0;
                }
                else {
                    count++;
                }
            }
            List<List<Integer>> possibleLists = new ArrayList<List<Integer>>();
            for(int i = 0 ; i < countOfNums.size(); ++i) {
                count = countOfNums.get(i);
                for(int j = possibleLists.size() - 1; j >= 0 && count > 0 ; --j) {
                    List<Integer> temp = possibleLists.get(j);
                    if(temp.get(temp.size() - 1) != uniqueNums.get(i) - 1) break;
                    temp.add(uniqueNums.get(i));
                    count--;
                }
                // rest of them will create new lists
                while(count != 0) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(uniqueNums.get(i));
                    count--;
                    possibleLists.add(temp);
                }
                // in the above 2 loops the current uniqueNums[i] will be added wherever possible either as a new list or appended to an already existing list...
            }
            // go over the lists and see if any list exist of size < 3
            for(List<Integer> eachList : possibleLists) {
                if(eachList.size() < 3) return false;
            }
            return true;
      
        }    
    }
    

Log in to reply
 

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