Left and Right Part Approach

                                Left & Right Approach 

        Some seems hard sequence problems can be solved by using this Left & Right approach, which simply break the sequence into left and right two parts and solve it accordingly. 

   Here is two example that can demonstrate this idea: 

         Example 1: Product of Array Except Self 

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Suggestion: Try it before you look at the analyze below. 

-----------------------------------------------------------------------------------------------------------------------

Analyze:  It is easy to come up with a simple 0(n^2) solution, and solve it by using division in 0(n) seems also not that hard. However, notice that if there is a 0 in our input array the division approach will not work properly and the question specifically requires solve it without division. 

Here is the elegant O(n) approach that using Left & Right approach: 

      The product except the element it self is actually can be break down to Left part product and Right part product. For example for number 3 in the example above, the Left part : 1 * 2 = 2 , the Right part: 4. So the product except 3 will be  2 * 4 = 8. 

      Here is the code based on this idea: 

  

            Example 2: Longest Consecutive Sequence 

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Try it out, see if you can get it. 

----------------------------------------------------------------------------------------------------------------------

 Analyze: The sequence here, again, can be divided into left and right parts, we can hold each elements of this array and to find its left possible sequence and right possible sequence. 

              The trick here is to put every number into Set that we could use contains() to find out weather we exist this number in input in O(1) time and remove it from our set after we do find it for not recounting the same sequence again. 

Hope you could use this approach to solve more problems :-) 

Enjoy Coding^^ 

Ye Jiang