Problem statement

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.
Link to problem

Example 1

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Solutions

Approach 1: Looping

First approach anyone would think of, pick an element and multiply all elements except that element.
Requires a nested loop which skyrockets the time complexity to $O(n^2)$.

However, the instructions say that an algorithm must be written that has time complexity of $O(n)$ and no more.

Implementation in Rust

fn product_except_self(numbers: Vec<i32>) -> Vec<i32> {
    let mut results: Vec<i32> = Vec::new();

    for i in 0..numbers.len() {
        let mut product: i32 = 1;
        for j in 0..numbers.len() {
            if i != j {
                product = product * numbers[j];
            }
        }
        results.push(product);
    }
    results
}

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
Runtime on LeetCode: Time Limit Exceeded

Approach 2: Division

Another approach which violates the leetcode instructions is usage of division.

The way division works in this case is, when you multiply all numbers, you can essentially divide it by the number that you don’t want, so it will run in $O(n)$ time complexity.

The reason this is not allowed is probably because of edge cases, such as multiplication by 0 and division by 0.

Most of your time would be spent in tackling the edge cases.
Would you like to make a contribution and add Rust implementation here?

Time complexity: $O(n)$

Approach 3: Before and After self

In this approach, we basically multiply the elements prior to self and after self.
Took me way too long to figure it out but it was worth it in the end.

The procedure is somewhat like this:

  1. Create pre, post and result vectors
  2. Initialize pre and post vectors with 1, their length must be same as input array
  3. For the pre vector
    1. Start iteration from the FIRST index, because the 0th index will be 1, always. Since there are no elements prior to 0th index element, we keep it at 1.
    2. Assign the product of previous number and the previous element in pre to the current pre element.
  4. For the post vector
    1. Start iteration from the SECOND LAST index, because there are no elements after the last index, we keep that at 1.
    2. While moving backwards, assign the product of next number and next element in the post vector to the current post element.

Pseudocode

create vector result 
create vector pre of input array's length
create vector post of input array's length

begin loop from 1 till end of input array's length
    assign pre[i-1] * numbers[i-1] to pre[i]

begin loop from input array's length - 1 till 0
    assign post[i+1] * numbers[i+1] to post[i]

begin loop from 0 till input array's length
    push post[i] * pre[i] to results

return results

Implementation in Rust

fn product_except_self(numbers: Vec<i32>) -> Vec<i32> {
    let mut results: Vec<i32> = Vec::new();
    let mut pre = vec![1; numbers.len()];
    let mut post = vec![1; numbers.len()];

    for i in 1..numbers.len() {
        pre[i] = (numbers[i-1] * pre[i-1]);
    }

    for i in (0..numbers.len() - 1).rev() {
        post[i] = numbers[i+1] * post[i+1];
    }

    for i in 0..numbers.len() {
        results.push(pre[i] * post[i]);
    }
    results
}

Time Complexity: $O(n)$
Runtime on LeetCode: $10$ms

You are probably thinking that the above could be improved by getting rid of pre and post vectors and working solely with results vector, which is an extra challenge that LeetCode mentioned at the end. Your thoughts are 100% valid. This can be done using just the results vector and another variable to manage post values.

Implementation in Rust

fn product_except_self(numbers: Vec<i32>) -> Vec<i32> {
    let mut pre = vec![1; numbers.len()];
    let mut post_op: i32 = 1;

    for i in 1..numbers.len() {
        pre[i] = (numbers[i-1] * pre[i-1]);
    }

    for i in (0..numbers.len()).rev() {
        pre[i] = post_op * pre[i];
        post_op *= numbers[i];
    }

    pre
}

Time Complexity: $O(n)$
Space Complexity: $O(1)$ according to LeetCode challenge since the results array is not considered.
Runtime on LeetCode: $15$ms