What is the time complexity of Three Equal Parts?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Three Equal Parts?

This problem uses Array, Math. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Three Equal Parts?

Insight 1: The most important observation is that all three parts must have the same number of ones. If the total number of ones is not divisible by 3, a split is impossible. Insight 2: After identifying the number of ones each part should have, the core logic involves finding a 'pattern' or canonical representation of the equal part. The third part is used as this pattern.

Which companies ask LeetCode 927. Three Equal Parts in interviews?

This problem is frequently asked at Hotstar.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Three Equal Parts - LeetCode 927 Solution

Q: How to solve Three Equal Parts?

The solution first counts the number of ones in the array. If this count is not divisible by 3, the problem is unsolvable. If the count is 0, any split will work (in this case, the solution provides a default split). Otherwise, we find the indices of the first one in each of the three parts (assuming the array can be divided into three equal parts). The third part starting from its first '1' is used as a template or 'pattern', and its length is determined. Then, the code verifies whether the first and second parts match this pattern by comparing their corresponding segments. If all parts match, the indices `i` and `j` are calculated based on the pattern's length and are returned.

Three Equal Parts - Complete Solution Guide

Three Equal Parts is LeetCode problem 927, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value. If it is possible, return any [i, j] with i + 1 < j , such that: arr[0], arr[1], ..., arr[i] is the first part, arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part. All three parts have equal binary values. If it is not possible, return [-1, -1] . Note

Detailed Explanation

The problem asks us to divide a binary array `arr` into three non-empty parts such that each part represents the same binary value (decimal equivalent). Leading zeros are allowed, meaning `[0,1,1]` and `[1,1]` are considered equal. We need to find indices `i` and `j` (where `i + 1 < j`) that define the boundaries of the three parts: `arr[0...i]`, `arr[i+1...j-1]`, and `arr[j...arr.length-1]`. If a valid split is possible, return `[i, j]`; otherwise, return `[-1, -1]`.

Solution Approach

The solution first counts the number of ones in the array. If this count is not divisible by 3, the problem is unsolvable. If the count is 0, any split will work (in this case, the solution provides a default split). Otherwise, we find the indices of the first one in each of the three parts (assuming the array can be divided into three equal parts). The third part starting from its first '1' is used as a template or 'pattern', and its length is determined. Then, the code verifies whether the first and second parts match this pattern by comparing their corresponding segments. If all parts match, the indices `i` and `j` are calculated based on the pattern's length and are returned.

Step-by-Step Algorithm

Step 1: Count the number of ones in the array.
Step 2: If the number of ones is not divisible by 3, return `[-1, -1]`. If the number of ones is zero, return `[0, 2]`.
Step 3: Calculate the number of ones each part should have (total_ones / 3).
Step 4: Find the start indices (s1, s2, s3) of the three parts based on the indices of '1's.
Step 5: Extract the 'pattern' or canonical representation using the last part (starting from s3).
Step 6: Compare the pattern with the segments of array starting from s1 and s2, return `[-1, -1]` if any of them does not match.
Step 7: Calculate the end index `i` of the first part and the start index `j` of the third part using the length of the pattern.
Step 8: Return the indices `[i, j]`.

Key Insights

Insight 1: The most important observation is that all three parts must have the same number of ones. If the total number of ones is not divisible by 3, a split is impossible.
Insight 2: After identifying the number of ones each part should have, the core logic involves finding a 'pattern' or canonical representation of the equal part. The third part is used as this pattern.
Insight 3: After finding the indices for the end of the first part and the start of the third part based on the pattern, the leading zeros or the 'tailing zeros' after each of these three parts is crucial to determine if the segments are really same.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Math.

Companies

Asked at: Hotstar.

Three Equal Parts | LeetCode 927

Hard

Array Math

Time: O(n)Space: O(n)

Solution Code

Available in:

class Solution {
    public int[] threeEqualParts(int[] arr) {
        List<Integer> ones = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                ones.add(i);
            }
        }
        
        int n = arr.length;
        int num_ones = ones.size();
        
        if (num_ones == 0) {
            return new int[] {0, 2};
        }

        if (num_ones % 3 != 0) {
            return new int[] {-1, -1};
        }
        
        int k = num_ones / 3;
        
        // Start indices of the 1s for each part's canonical representation
        int s1 = ones.get(0);
        int s2 = ones.get(k);
        int s3 = ones.get(2 * k);
        
        // The pattern is defined by the third part, from its first 1 to the end
        int[] pattern = Arrays.copyOfRange(arr, s3, arr.length);
        int len_pattern = pattern.length;
        
        // The segments in the first two parts must match this pattern
        if (!Arrays.equals(Arrays.copyOfRange(arr, s1, s1 + len_pattern), pattern)) {
            return new int[] {-1, -1};
        }
        
        if (!Arrays.equals(Arrays.copyOfRange(arr, s2, s2 + len_pattern), pattern)) {
            return new int[] {-1, -1};
        }
            
        // If they match, we can determine the partition points
        // i is the end of the first part
        // j is the start of the third part
        int i = s1 + len_pattern - 1;
        int j = s2 + len_pattern;
        
        return new int[] {i, j};
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 927: Three Equal Parts - Detailed explanation and solution approaches.

Topics

Array Math

Companies

Hotstar

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:927

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Count the number of ones in the array.
2
Step 2: If the number of ones is not divisible by 3, return `[-1, -1]`. If the number of ones is zero, return `[0, 2]`.
3
Step 3: Calculate the number of ones each part should have (total_ones / 3).
4
Step 4: Find the start indices (s1, s2, s3) of the three parts based on the indices of '1's.
5
Step 5: Extract the 'pattern' or canonical representation using the last part (starting from s3).
6
Step 6: Compare the pattern with the segments of array starting from s1 and s2, return `[-1, -1]` if any of them does not match.
7
Step 7: Calculate the end index `i` of the first part and the start index `j` of the third part using the length of the pattern.
8
Step 8: Return the indices `[i, j]`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the loops used to find the positions of '1's and to compare the patterns. Since we iterate through the array a constant number of times (independent of the size of the array), the time complexity is linear, O(n). The space complexity comes from storing the indices of the '1's in the `ones` array/list/vector, which can have up to n elements in the worst case (all elements are '1'). Furthermore, copies of the array may be created of size up to n, leading to O(n) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Convert to Integer and Divide

Convert each part of the array into an integer. Then check whether those integers are same.

Time: O(n)Space: O(1)

Trade-offs: This approach involves converting binary subarrays into decimal numbers. This might work for smaller arrays, but for larger arrays, you might encounter integer overflow issues, limiting its applicability. Also, converting to decimal and comparing values will not work as leading zeros can be present which will change the decimal value. The described solution avoids this issue.

✨

Key Insights

1Insight 1: The most important observation is that all three parts must have the same number of ones. If the total number of ones is not divisible by 3, a split is impossible.
2Insight 2: After identifying the number of ones each part should have, the core logic involves finding a 'pattern' or canonical representation of the equal part. The third part is used as this pattern.
3Insight 3: After finding the indices for the end of the first part and the start of the third part based on the pattern, the leading zeros or the 'tailing zeros' after each of these three parts is crucial to determine if the segments are really same.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Array with all zeros. The solution handles this correctly by returning `[0, 2]`. This ensures that the three parts are `[0]`, `[0]`, and the rest of the array which is empty string, which will be empty string as well, or two empty strings between all leading zeros.
Edge case 2: Array with a number of ones that's not divisible by 3. The solution returns `[-1, -1]` in this case, as no valid split exists.
Edge case 3: An array where the equal part cannot be matched because of leading zeros at either s1 or s2 or s3. These are handled by using the pattern found at S3, whose length is derived properly.
Edge case 4: An array with 3 ones and all other elements are zeros. The pattern matching is still applicable in this scenario where the ones are located adjacently. E.g. [0,0,1,1,1,0,0]. This edge case has been handled correctly by checking the s1+len_pattern and s2+len_pattern.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the total number of ones is not divisible by 3. This will lead to incorrect results.

✗Common mistake 2: Incorrectly calculating the indices `i` and `j`, particularly when dealing with leading zeros. It's crucial to consider the pattern length and the positions of the ones.

✗Common mistake 3: Integer overflow if converting large binary arrays into integers for comparison.

✗Common mistake 4: Not considering the possibility of the entire array being zeros, or having no ones, resulting in out-of-bounds errors or incorrect logic.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Data transmission integrity. Imagine a data stream (represented as a binary array) needs to be divided into three equal, verifiable chunks. This problem's solution helps determine if such a division is possible and where the chunks should be split.

🏦Real-world scenario 2: Resource allocation: Think of splitting a resource represented by binary data into three equal parts across different servers or processes. This problem helps ensure fair allocation.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 28, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Three Equal Parts"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?