My one-pass Java solution without extra spaces


  • 30
    D

    One pass, if don't count the initialization of the 'result'...

        int[] result = new int[nums.length];
        for (int i = 0; i < result.length; i++) result[i] = 1;
        int left = 1, right = 1;
        for (int i = 0, j = nums.length - 1; i < nums.length - 1; i++, j--) {
            left *= nums[i];
            right *= nums[j];
            result[i + 1] *= left;
            result[j - 1] *= right;
        }
        return result;
    

    edit 2016/04/05:

    EXPLAINATION:

    Thinking of the 'nums' array [1, 2, 3, 4, 5, 6], and the 'result' array [1, 1, 1, 1, 1, 1]. Every number in 'nums' will be multiplied in 'result' array except itself, then we will get the map below:

      1 2 3 4 5 6
      -----------
    1|  1 1 1 1 1
    2|2   2 2 2 2
    3|3 3   3 3 3
    4|4 4 4   4 4
    5|5 5 5 5   5
    6|6 6 6 6 6
    
    (horizontal axis is nums array, vertical axis is multiplied times)
    

    Noticed the regular pattern of the upper triangular and lower triangular. Using integers to store the products of the lower and upper triangulars, then we can do it in one pass:

    • i : left index of the nums array
    • j : right index of the nums array
    • left : left products multiplied from nums[0] to nums[i].
    • right : right products multiplied from nums[j] to nums[nums.length - 1].

    We multiply left to result[i + 1] ((i, i + 1) in the uppper triangular),

    and multiply right to result[j - 1] ((j, j - 1) in the lower triangular),

    finally we have calculated the products of the nums except current.

    Sorry for my poor English...= =!
    Checking more of my solutions at: https://github.com/dss886/LeetCode/tree/master/src/leetcode


  • 0
    A

    Great solution!
    Can you explain how is the current element getting skipped during multiplication?


  • 0
    D

    I update the post and explain it :)


  • 0
    A

    Thanks a lot!!Got it!!!


  • 0

    Your English is great!


  • 0
    K

    u are awsm....


  • 0
    E

    Although this solution has the same time complexity as doing a two pass (you're just doing both processing in the single pass so they should be the same), I agree that having to write one loop is less tedious than writing 2 separate loops.


Log in to reply
 

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