A Possible Solution For [Leetcode 238. Product of Array Except Self]

For those who feels interested to give it a try, the coding puzzle can be found here.

The puzzle is as follows:

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].

And the requirements or challenges are:

1. Solve it without division and in O(n).

2. Solve it with constant space complexity.

The following is the solution that I came up with (in Swift). I thought it was the best because it only loops the array once while all other solutions that I found around the web loops the array at least twice. But it doesn't conform to the second requirement about the space complexity because of the recursive call, unfortunately. 

Besides, for some odd reason, this solution will generate a runtime error when the array holds more than 34892 elements. I can't seem to find any logic issues in the code so far (If you happen to read this article, please do get in touch if you found any issues within the code). Fyi, I'm using Xcode 7.3 which comes with Swift 2.2. Not sure if it is a compiler issue.

Here is the code:

func productExceptSelf(nums: [Int]) -> [Int] {

    func product(inout nums: [Int], _ index: Int, _ leftProduct: Int) -> Int {

        let number = nums[index]

            

        if index == nums.count-1 {

            nums[index] = leftProduct

            return number

        }

        else {

            let rightProduct = product(&nums, index + 1, number * leftProduct)

            nums[index] = leftProduct * rightProduct

            return rightProduct * number

        }

    }

    

    var numbers = nums

    _ = product(&numbers, 0, 1)

    return numbers

}