Tuesday, December 12, 2023

Leetcode type problem - Sub-Arrays problem

 Generate number of sub arrays with a particular sum: E.g. nums = [1,1,1] with sum 2

arr = [1,1,1]
SUM =2
#arr = [1,2,2,3,4,5]
#SUM = 5

sub_arrays = []
arr = arr.sort

arr.each_with_index do |n, index|
  if n == SUM
    sub_arrays << [n]
    next
  end
  rest_of_array = arr[(index+1)..-1]
  temp_arr = [n]

  rest_of_array.each do |m|
    temp_arr << m
    if temp_arr.sum == SUM
      # We found a sub_array!
      sub_arrays << temp_arr
      # There might be duplicates of m, so let us remove m from temp_arr and continue
      temp_arr = temp_arr[0..temp_arr.length-2]
    end
    if temp_arr.sum < SUM
      # do nothing; we can continue to add more elements
    end
    if temp_arr.sum > SUM
      # discard all elements except n
      temp_arr = [n]
    end
  end
end

puts sub_arrays.to_s

No comments:

Post a Comment

Followers

Blog Archive