Split an Array into Equal Sum Subarrays (with Google Software Engineer)

Richard Su explains how to split an array into equal sum subarrays. Find if it is possible to divide an array of integers greater than zero into two subarrays without changing the order of the entries. Print the two subarrays.

Chapters -
00:00 - Introduction
00:41 - Question
00:54 - Clarifying questions
01:46 - Answer
06:40 - Implementation
13:06 - Test cases
16:07 - Interview analysis
18:39 - Tips

Watch more videos here:

ABOUT US:
Did you enjoy this interview question and answer? Want to land your dream career? Exponent is an online community, course, and coaching platform to help you ace your upcoming interview. Exponent has helped people land their dream careers at companies like Google, Microsoft, Amazon, and high-growth startups. Exponent is currently licensed by Stanford, Yale, UW, and others.

Our courses include interview lessons, questions, and complete answers with video walkthroughs. Access hours of real interview videos, where we analyze what went right or wrong, and our 1000+ community of expert coaches and industry professionals, to help you get your dream job and more!

#softwareengineering #amazon #coding #leetcode #equalsum #subarray #google #tech #entrepreneurship #exponent

[massimomonticelli]

Thanks for the video! Really appreciated. Assuming non negative numbers in the list, the loop can also exit - returning None - if the running sum at some point gets greater than the target. Thanks again, Massimo.

[latenightjamming]

Hi team
I guess this is wrong solution, with input [1, 3, 2] this will fail as he is trying only to put continuous elements.
Thats why his [1, 2, 3] worked but [1, 3, 2] will not.

[yiannig]

I found it amusing that he preached about mastering the programming language for interviews, yet stumbled over range functions.

[shenjun]

The solution is dependent on if the array is sorted?

[Sunny-wiwm]

Please correct me if I am wrong, I don't think the solution is correct. Does it work for 1, 3, 3, 5 even if it is sorted? I believe it would return None instead of [1, 5] [3, 3]. May be I missed something.

[Boringpenguin]

A related but way harder problem would be to find any two integer subsequence (not necessarily just splitting the original one up) with equal sum
e.g. a = [4, 2, 12, 5, 3, 21], the two subarrays would be [2, 12] and [3, 21], with sum = 24

[carefree_ladka]

Google would never ask such questions. I mean it's simple to code .

[latenightjamming]

I have tried writing the whole code which is bit more generic and not only for 2 splits but also for k number of splits.

def split_array(inp_arr, st_ind, end_ind)
base_array_st = []
base_array_end = []
base_array_st = inp_arr[0...st_ind] if st_ind > 0
derived_array = inp_arr[st_ind..end_ind]
base_array_end = if end_ind < (inp_arr.length-1)
puts + base_array_end).inspect}"
# Heree dervied_Array is to be transfered
return derived_array, (base_array_st + base_array_end)
end


def dfs(curr_sub_arrs, k, target_sum, sub_arr_ind = 0)
puts "---came
sub_arr_to_operate = curr_sub_arrs[sub_arr_ind]
if sub_arr_ind < (k-1)
value_with_current_subarr = dfs(curr_sub_arrs, k, target_sum, (sub_arr_ind+1)) if sub_arr_to_operate.sum == target_sum
return true if value_with_current_subarr
else
return sub_arr_to_operate.sum == target_sum
end
curr_sub_arr_length = sub_arr_to_operate.length
curr_diff = 1
do |total_elements_to_shift|
curr_sub_arr_length.times do |st_ind|
end_ind = st_ind + total_elements_to_shift - 1
temp_arr = sub_arr_to_operate
derived_array, base_array = split_array(sub_arr_to_operate, st_ind, end_ind)
next if base_array.sum != target_sum
new_curr_sub_arrays = curr_sub_arrs.clone
= base_array
= derived_array + curr_sub_arrs[sub_arr_ind+1]
return true if dfs(new_curr_sub_arrays, k, target_sum, (sub_arr_ind+1))
end
end
return false
end

def divide_arr(arr, k)
puts "--input---#{arr.inspect}"
return -1 if arr.nil? || k.nil? || arr.length < k

total_sum = arr.sum
return -1 if (total_sum % k) != 0
sum_of_each_subarr = total_sum/k
starting_sub_arrs = []
temp_arr = arr
(1...k).each do |arr_ind|
new_val = temp_arr.pop
starting_sub_arrs << [new_val]
end
starting_sub_arrs << temp_arr
starting_sub_arrs.reverse!
puts
dfs(starting_sub_arrs, k, sum_of_each_subarr)
end


puts divide_arr([2, 3, 4, 5, 1, 2, 3], 4)
puts divide_arr([1, 2, 3], 2)
puts divide_arr([1, 3, 2], 2)

[kharljohnrayala]

won't work with these two samples:
sample 1 = [1, 4, 4, 5, 6, 6, 10]
sample 2 = [1, 2, 5, 6, 12]
because the correct subarrays for my examples don't have consecutive indexes from original arrays

[r.]

Why do we assume the list is sorted? Good solution otherwise

[parthgabhane]

At first i thought the left person is a girl

[stevefoo]

Kool solution. I came up with another one to use two pointers: one at the start of the list and one at the end of list. As you increment and decrement each pointer you add up the sum in two different variables. You would stop when each sum is equal to each other and the start poiner is sequential to the end pointer. If the pointers ever equal one another then there is no equal sub-array.

[linshengred]

Is this interview result will be hire / lean hire or strong hire?

[YTGhostCensorshipCanSuckMe]

sum the array and divide by 2. That is the target sum. If the division by two doesn't yield an integer, then you know there is not a solution for sure. Then try to solve using a monte-carlo approach by selecting an element at random from array A and introducing to an initially empty array B. Maintain a running sum of B. Retain the move if the sum of the new array is less than the target sum. If it goes over, then discard the attempt and additionally discard one of the previous entries at random (with say 50% probability), so that you don't get trapped in a local minima. This is essentially an error minimisation routine, and you can use it to get the closest solution if an explicit solution isn't necessarily available. Continue until the target is achieved, or error term is not improving (in the event you are unsure a solution exists).

[technovinitySystem]

will this solution work in case of this [1, 3, 7, 2, 11] ?