Java O(n) Time O(n) Space


  • 51
    1. We iterate through the array once to get the frequency of all the elements in the array
    2. We iterate through the array once more and for each element we either see if it can be appended to a previously constructed consecutive sequence or if it can be the start of a new consecutive sequence. If neither are true, then we return false.
    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
        for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);
        for (int i : nums) {
            if (freq.get(i) == 0) continue;
            else if (appendfreq.getOrDefault(i,0) > 0) {
                appendfreq.put(i, appendfreq.get(i) - 1);
                appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);
            }   
            else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) {
                freq.put(i+1, freq.get(i+1) - 1);
                freq.put(i+2, freq.get(i+2) - 1);
                appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
            }
            else return false;
            freq.put(i, freq.get(i) - 1);
        }
        return true;
    }
    

  • 0
    I
    This post is deleted!

  • 1
    T

    great solution!!! Emulate your method!!!

    public class Solution {
        public boolean isPossible(int[] nums) {
           if(nums==null || nums.length<3) return false;
           Map<Integer,Integer> map = new HashMap<>();
           for(int ele:nums){
               map.put(ele,map.getOrDefault(ele,0)+1);
           }
           Map<Integer,Integer> appendMap = new HashMap<>();
           for(int ele:nums){
              if(map.getOrDefault(ele,0)<=0){
                  continue;
              }
               
              if(appendMap.getOrDefault(ele,0)>0){
                  appendMap.put(ele,appendMap.get(ele)-1);
                  appendMap.put(ele+1,appendMap.getOrDefault(ele+1,0)+1);
              }else if(map.getOrDefault(ele+1,0)>0&&map.getOrDefault(ele+2,0)>0){
                   map.put(ele+1,map.getOrDefault(ele+1,0)-1);
                   map.put(ele+2,map.getOrDefault(ele+2,0)-1);
                   appendMap.put(ele+3,appendMap.getOrDefault(ele+3,0)+1);
              }else{
                  return false;
              }
              
              map.put(ele,map.get(ele)-1);
           }
            
            return true;
           
        }
    }
    
    
    
    

  • 0
    Y

    Wow, smart solution


  • 1

    @compton_scatter said in Java O(n) Time O(n) Space:

            appendfreq.put(i, appendfreq.get(i)-1);
            appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0)+1);
    

    Hi, I somewhat get the idea, but could you help explain about these two lines, it seems you want to use appendFreq to monitor the freq value change?

    Thanks!


  • 7
    T

    @coder42 These two lines are used to track previous consecutive sequences next elements' values. If current element can be next element of one of previous consecutive sequences, it means we can append it to that sequence. We don't need to worry about whether we can use this element to be a new start point of a new consecutive sequence, that's because even though the current element can be a new start point of a consecutive sequence, we can simply append those consecutive elements following this current element at the end of the previous consecutive sequence.


  • 5
    D

    C++ version

    bool isPossible(vector<int>& nums)
    {
    	unordered_map<int, int> freq, afreq;
    	for (auto &e : nums)
    		freq[e]++;
    	for (auto &e : nums)
    	{
    		// the number has been used
    		if (freq[e] == 0)    continue;
    		// the number follow after other sequence
    		else if (afreq.find(e) != afreq.end() && afreq[e]>0) {
    			afreq[e]--;
    			afreq[e + 1]++;
    		}
    		// the number form a new sequence
    		else if (freq.find(e + 1) != freq.end() && freq[e + 1]>0
    			&& freq.find(e + 2) != freq.end() && freq[e + 2]>0) {
    			freq[e + 1]--;
    			freq[e + 2]--;
    			afreq[e + 3]++;
    		}
    		// can't deal with this number
    		else    return false;
    		freq[e]--;
    	}
    	return true;
    }
    

  • 0

    @tiandiao123 Thanks! This observation is really genius!


  • 1
    Z

    excellent!!!
    It takes me a little time to understand your answer.
    It would be better if you write some comments.


  • 2
    K

    @compton_scatter said in Java O(n) Time O(n) Space:

    public boolean isPossible(int[] nums) {
    Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
    for (int i : nums) freq.put(i, freq.getOrDefault(i,0)+1);
    for (int i : nums) {
    if (freq.get(i) == 0) continue;
    else if (appendfreq.getOrDefault(i,0) > 0) {
    appendfreq.put(i, appendfreq.get(i)-1);
    appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0)+1);
    }
    else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) {
    freq.put(i+1, freq.get(i+1) - 1);
    freq.put(i+2, freq.get(i+2) - 1);
    appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
    }
    else return false;
    freq.put(i, freq.get(i) - 1);
    }
    return true;
    }

    Could you add some comments? Thx


  • 1

    @compton_scatter Could you please explain your algorithms please?
    I upvoted it for its brevity and correctness, but I'm sure some more inline comments will make it more popular.


  • -2
    M
    This post is deleted!

  • 0

    @donggua_fu said in Java O(n) Time O(n) Space:

    	else if (afreq.find(e) != afreq.end() && afreq[e]>0) {
    		afreq[e]--;
    		afreq[e + 1]++;
    	}
    

    Hey @donggua_fu Thanks very much for you genius posted a commented code. However, could you help to explain more about the "afreq" implementation?

    More specifically, could you help to explain what "afreq[e]--;" and "afreq[e + 1]++;" stand for? I know you are trying to use "afreq" to track whether "current element can be next element of one of the previous consecutive sequences (quote from @tiandiao123 )" .However, I am still confused why these two line work.
    It would be great to give us some clues of mathematical correctness behind this algorithm. (But this solution is smart and clear! Thanks!)


  • 1
    M

    In my algorithm, I first check whether nums[i] can create a new subsequence; if not, then check whether it can extend existing subsequences.
    But it passed 178/180 test cases, can anyone tell me where was wrong? Thank you!


  • 1
    D

    @MichaelZZZ Consider this case: 1 2 3 4 5 5 6 7. If you create a new subsequence first you will get 1 2 3 then 4 5 6 then return false. But actually the answer is true because we can split the array by 1 2 3 4 5 and 5 6 7.


  • 5

    C++ same clean code beats 100%. Using the C++ map property of having a default value of 0.

    class Solution {
    public:
        bool isPossible(vector<int>& nums) {
            unordered_map<int, int> dict, temp;
            for (auto& ele: nums) dict[ele]++;
            for (auto& ele: nums){
                if (dict[ele]==0)   //if the ele is already used in some sequence
                    continue;
                else if (temp[ele]>0){  //if the ele can be added in the last consecutive sequence
                    dict[ele]--;
                    temp[ele]--;
                    temp[ele+1]++;
                    
                }else if (dict[ele+1]>0 && dict[ele+2]>0){ //this ele should form a consecutive sequence by itself since it cannot be appended to a previous sequence
                    dict[ele]--;
                    dict[ele+1]--;
                    dict[ele+2]--;
                    temp[ele+3]++;
                }else //doesn't belong to any consecutive sequence
                    return false;
            }
            return true;
        }
    };
    

  • 2

    Just for fun a dense C++ version.

    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> f, a;
        for (int i : nums) f[i]++;
        for (int i : nums)
            if (f[i] && f[i]-- && !(a[i] && a[i]-- && ++a[i+1]) && !(f[i+1]-- && f[i+2]-- && ++a[i+3]))
                return false;
        return true;
    }

  • 1
    J

    How come it returns "true" for 1,2,3,4,5 array?


  • 4

    What does the value in the appendfreq map stand for?


  • 0
    Z

    @john700 Yea, same question.


Log in to reply
 

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