Java solution with comments. Time O(n). Space constant.


  • 0
    F

    Time complexity: O(n)
    Space: constant (except the output array).

    class Solution {
        public int[] productExceptSelf(int[] nums) {
          int[] output = new int[nums.length];
    
          # First pass. Calculate a rolling product forward and save to output.
          int product=1;
          for (int i = 0; i < nums.length; i++) {
            output[i] = product;
            product *= nums[i];
          }
          
          # Second pass. Calcuate a rolling product backward and combine with
          # the result from first pass.
          product = 1;
          for (int i = nums.length -1; i >= 0; i--) {
            output[i] *= product;
            product *= nums[i];
          }
          
          return output;
        }
    }
    

Log in to reply
 

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