How do you solve Three Equal Parts on LeetCode?

Three Equal Parts (LeetCode #927) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The total number of 1s must be divisible by 3 to split the array into three equal parts.

What is the brute force solution for Three Equal Parts?

The brute force approach for Three Equal Parts is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible way to split the array into three parts and comparing their binary values. This method is straightforward but inefficient as it checks all combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Three Equal Parts?

Three Equal Parts uses the following concepts: Array, Math. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Three Equal Parts?

Always start by understanding the problem and identifying edge cases. Think about the properties of the data (like the number of 1s) that can help simplify the problem. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Three Equal Parts?

Not checking if the total number of 1s is divisible by 3. Failing to handle the case where all elements are zeros.

#927

Three Equal Parts

Hard

ArrayMathHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages the fact that all three parts must have the same number of 1s. By counting the total number of 1s and ensuring they can be evenly divided into three parts, we can efficiently find the split points.

⚙️

Algorithm

3 steps

1Step 1: Count the total number of 1s in the array. If it's not divisible by 3, return [-1, -1].
2Step 2: Identify the starting indices of each of the three parts based on the positions of the 1s.
3Step 3: Compare the three parts starting from their respective indices to ensure they are equal, adjusting for any trailing zeros.

solution.py24 lines

1# Full working Python code
2
3def threeEqualParts(arr):
4    total_ones = sum(arr)
5    if total_ones % 3 != 0:
6        return [-1, -1]
7    if total_ones == 0:
8        return [0, 2]
9    first, second, third = -1, -1, -1
10    count = 0
11    for i in range(len(arr)):
12        if arr[i] == 1:
13            count += 1
14            if count == 1:
15                first = i
16            elif count == total_ones // 3 + 1:
17                second = i
18            elif count == 2 * (total_ones // 3) + 1:
19                third = i
20    while third < len(arr) and arr[first] == arr[second] == arr[third]:
21        first += 1
22        second += 1
23        third += 1
24    return [first - 1, second] if first > second else [-1, -1]

ℹ

Complexity note: The time complexity is O(n) because we make a single pass through the array to count the 1s and another pass to find the split points. The space complexity is O(1) since we only use a few variables to store indices.

1The total number of 1s must be divisible by 3 to split the array into three equal parts.
2Trailing zeros in the parts can be ignored as they do not affect the binary value.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.