Java easy-understanding solution by one pass


  • 0
    J

    I took two lists recording segments(start<=end, as the "13" patterns) ever passed and sorted in ascending order.

        public boolean find132pattern(int[] nums) {
            List<Integer> start = new ArrayList(), end = new ArrayList();
            for (int x:nums) {
                int p = find132(x,start,end);
                if (p>=0 && p<start.size() && x>start.get(p) && x<end.get(p)) return true;
                if (p<0) {
                    start.add(0,x);
                    end.add(0,x);
                } else if (x>end.get(p)) {
                    end.set(0,x);
                    for (int i=p; i>=1; i--) {
                        start.remove(i);
                        end.remove(i);
                    }
                }
            }
            return false;
        }
        
        private int find132(int x, List<Integer> start, List<Integer> end) {
            if (start.isEmpty()) return -1;
            for (int i=0; i<start.size(); i++)
                if (start.get(i)>=x) return i-1;
    
            return start.size()-1;
        }
    

Log in to reply
 

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