O(n*logn) treeMap + explanation


  • 0
    A

    The idea is to try to fix the nums[i] as a maximum value. The next step is to find minimum from our prefix. Then try to find if there exists the value in suffix which is greater than minimum and less than nums[i]. To find that value fast we can use tree map to count each number's occurrences and use it's lower() function.

    public class Solution {
        public boolean find132pattern(int[] nums) {
            if (nums.length<=2) return false;
            TreeMap<Integer, Integer> counts = getCounts(nums);
            decrease(counts, nums[0], -1);
            int min = nums[0];
            
            for (int i=1; i<nums.length; i++) {
                decrease(counts, nums[i], -1);
                Integer lower = counts.lowerKey(nums[i]);
                if (lower!=null && lower>min) return true;
                min = Math.min(min, nums[i]);
            }
            return false;
        }
        
        private void decrease(TreeMap<Integer, Integer> counts, int key, int adder) {
            if (counts.containsKey(key)) {
                counts.put(key, counts.get(key)+adder);
                if (counts.get(key)<=0) counts.remove(key);
            }
        }
        
        private TreeMap<Integer, Integer> getCounts(int nums[]) {
            TreeMap<Integer, Integer> counts = new TreeMap<>();
            for (int val: nums) {
                counts.put(val, counts.getOrDefault(val,0) + 1);
            }
            return counts;
        }
    }
    

Log in to reply
 

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