C# - simple and accepted but O(n^2), no extra space


  • 0

    Here is one that is pretty simple, but not optimal as it is an O(n^2) solution, however, it uses no extra space. You can see the inefficient part comes from the repeated search for element k. The better O(n) solutions use a Stack to avoid this repeated work.

        public bool Find132pattern(int[] nums) 
        {
            int i = 0;
            
            while (i < nums.Length - 2)
            {
                // advance i while numbers are decreasing
                while (i < nums.Length - 1 && nums[i+1] <= nums[i]) i++;
                
                // advance j while numbers are increasing and greater than nums[i]
                int j = i + 1;
                while (j < nums.Length - 1 && (nums[j] <= nums[i] || nums[j+1] >= nums[j])) j++;
                
                // test elements beyond j for value between nums[i] and nums[j]
                for (int k = j + 1; k < nums.Length; k++)
                {
                    if (nums[k] > nums[i] && nums[k] < nums[j]) return true;
                }
                
                // not found, restart after j
                i = j + 1;
            }
            
            return false;
        }
    

Log in to reply
 

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