My solution beats 100% java solutions


  • 67
    A

    The idea is simply. The product basically is calculated using the numbers before the current number and the numbers after the current number. Thus, we can scan the array twice. First, we calcuate the running product of the part before the current number. Second, we calculate the running product of the part after the current number through scanning from the end of the array.

    public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int leng = nums.length;
        int[] ret = new int[leng];
        if(leng == 0)
            return ret;
        int runningprefix = 1;
        for(int i = 0; i < leng; i++){
            ret[i] = runningprefix;
            runningprefix*= nums[i];
        }
        int runningsufix = 1;
        for(int i = leng -1; i >= 0; i--){
            ret[i] *= runningsufix;
            runningsufix *= nums[i];
        }
        return ret;
        
    }
    

    }


  • 0
    L

    This idea is very smart..


  • 1
    S

    Leet code's performance measure is not consistent. The same solution gave me 50% as well.


  • 0
    L

    that's not the point dude! This idea is unbeatable...


  • 0
    A

    Brilliant solution....


  • 1
    M

    The naming of prefix and sufix really helped me to understand the thought process


  • 0

    Your explainstion is cleary!


  • -5
    S

    Is this really O(1) space?? Because we create a new array and the length of new array is the length of nums array, so isn't this O(n) space?


  • 0
    R

    Follow up:
    Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)


  • 0
    P

    This is a really genius idea! Different way make different efficiency!


  • 0
    J

    I like the the code itself, very readable from the code itself. I just get it after reading the code. xD The explanation is also very nice.


Log in to reply
 

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