HackerRank Coding Interview 3. Split the Array

Time to complete — 30minutes

Question Type = Medium

Asked in = Microsoft, Uber, Netflix, Bloomberg, Morgan Stanley, Apple, AMAZON, Google

Skills: arrays, enumeration, Binary Search, combinatorics

Insights — It should be read very carefully read and you must ask questions in between.

Question —

The array nums contains n non-negative integers. Determine the number of ways to split nums into three non-empty subarrays A1, A2, and A3 with the sum of elements of the subarrays as S1, S2, and S3 respectively, such that S1, S2, and S3 satisfy S2 ≤ S1 + S3.

Return the value modulo (10⁹ + 7).

Note:

• A subarray is a contiguous part of an array. For example, the subarrays of [1, 2, 3] are [1], [2], [3], [1,2], [2,3] and [1,2,3].

All three subarrays should contain at least 1 element.

• Each element of the array must belong to one of the three subarrays A1, A2, or A3.
• The subarray A1 must be followed by subarray A2 which must then be followed by A3. For example in the array [1, 4, 3] it is not possible to take A1 = 1, A2 = 3, and A3 = 4. We must take A1 = 1, A2 = 4 and A3 = 3 only.

Example

nums = [1,2,3,4]

There are 3 valid solutions:

1. [1], [2], [3, 4], here S1 = 1, S2 =…