# Arrays - Get Products of all other elements in Ruby

# Algorithm challenge description:
# Given an array of integers, return a new array such that
# each element at index `i` of the new array is the product of
# all the numbers in the original array except the one at `i`.

#
# This file solves the algorithm in 3 approaches:
#
# 1. Brute force
# 2. Left and Right product lists
# 3. O(1) space approach
#

#
# 1. Brute force solution
#
def calculate_products_of_all_other_elements(nums)
  product_of_other_elements = Array.new(nums.count, 1)

  nums.count.times do |i|
    nums.count.times do |j|
      next if i == j

      product_of_other_elements[i] = product_of_other_elements[i] * nums[j]
    end
  end

  product_of_other_elements
end

puts(calculate_products_of_all_other_elements([1, 2, 3]))

#
# Approach 2: Left and Right product lists
#

# Complexity analysis
#
# Time complexity: O(N) where N represents the number of elements in the input
# array. We use one iteration to construct the array prefix_products, one to construct
# the array suffix_products and one last to construct the answeranswer array using L and R.
# Space complexity: O(N) used up by the two intermediate arrays that
# we constructed to keep track of product of elements to the left and right.

# Generates prefix products
# prefix_products[i] contains the product of all the elements to the left
# Note: for the element at index '0', there are no elements to the left,
# so the prefix_products[0] would be 1
def build_prefix_products(nums)
  prefix_products = []

  nums.each do |num|
    prefix_products << if prefix_products.count > 0
                         prefix_products.last * num
                       else
                         num
                       end
  end

  prefix_products
end

# Generates suffix products
# suffix_products[i] contains the product of all the elements to the right
# Note: for the element at index 'length - 1', there are no elements to the right,
# so the suffix_products[length - 1] would be 1
def build_suffix_products(nums)
  suffix_products = []

  nums.reverse.each do |num|
    suffix_products << if suffix_products.count > 0
                         suffix_products.last * num
                       else
                         num
                       end
  end

  suffix_products
end

# Builds output
# For the first element, suffix_products[i] would be product except self
# For the last element of the array, product except self would be prefix_products[i]
# Else, multiple product of all elements to the left and to the right
def output(prefix_products, suffix_products, nums)
  result = []

  nums.count.times do |index|
    result << if index == 0
                suffix_products[index + 1]
              elsif index == nums.count - 1
                prefix_products[index - 1]
              else
                (prefix_products[index - 1] * suffix_products[index + 1])
              end
  end

  result
end

# Generate result from the product of prefixes and suffixes
def products(nums)
  prefix_products = build_prefix_products(nums)
  suffix_products = build_suffix_products(nums)
  suffix_products = suffix_products.reverse

  output(prefix_products, suffix_products, nums)
end

puts(products([1, 2, 3]))
# => [6, 3, 2]

#
# Approach 3: O(1) space approach
#

# This approach is essentially an extension of the approach 2.
# Basically, we will be using the output array as one of L or R and we will
# be constructing the other one on the fly.

# Complexity analysis
#
# Time complexity: O(N) where N represents the number of elements in the input
# array. We use one iteration to construct the array L, one to update the array
# answer.

# Space complexity: O(1) since don't use any additional array for our
# computations. The problem statement mentions that using the answer
# array doesn't add to the space complexity.

def products(nums)
  return [] if nums.count < 2

  res = [1]

  # res[i] contains the product of all the elements to the left
  # Note: for the element at index '0', there are no elements to the left,
  # so the res[0] would be 1
  (0..(nums.count - 2)).each do |i|
    num = nums[i]
    res << num * res[i]
  end

  # product contains the product of all the elements to the right
  # Note: for the element at index 'length - 1', there are no elements to the right,
  # so the product would be 1
  product = 1

  (nums.count - 1).downto(1) do |i|
    num = nums[i]
    # For the index 'i', product would contain the
    # product of all elements to the right. We update product accordingly.
    res[i - 1] *= (product * num)
    product *= num
  end

  res
end

puts(products([1, 2, 3]))
# => [6, 3, 2]