Facebook Coding Interview Question | Leetcode 689 | Maximum Sum of 3 Non-Overlapping Subarrays

In this video, we introduce how to solve the "Maximum Sum of 3 Non-Overlapping Subarrays" question which is used by big tech companies like Google, Facebook, Amazon in coding interviews. We also cover how to behave during a coding interview, e.g. communication, testing, coding style, etc.

Please subscribe to this channel if you like this video. I will keep updating this channel with videos covering different topics in interviews from big tech companies.

[angelsancheese]

# Python version of your code
class Solution:
def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
len_nums = len(nums)
sd_sum = [0 for _ in range(len_nums)]
i = 0
sum_window = 0
while i < len_nums:
sum_window = sum_window + nums[i]
if i >= k:
sum_window = sum_window - nums[i-k]
sd_sum[i] = sum_window
i = i + 1
left_max = [0 for _ in range(len_nums)]
largest_idx = 0
for i, sum_window in enumerate(sd_sum):
if sum_window > sd_sum[largest_idx]:
largest_idx = i
left_max[i] = largest_idx
right_max = [0 for _ in range(len_nums)]
largest_idx = len_nums - 1
i = len_nums - 1
while i >= 0:
# needs to be >= because problem is asking for smallest lexicographically
if sd_sum[i] >= sd_sum[largest_idx]:
largest_idx = i
right_max[i] = largest_idx
i = i - 1
arr_idx = [0 for _ in range(3)]
max_sum = -1
mid = 2 * k - 1
while mid < len_nums - k:
left = left_max[mid-k]
right = right_max[mid+k]
total_sum = sd_sum[left] + sd_sum[mid] + sd_sum[right]
if total_sum > max_sum:
max_sum = total_sum
arr_idx[0] = left - k + 1
arr_idx[1] = mid - k + 1
arr_idx[2] = right - k + 1
mid = mid + 1
return arr_idx