What is the time complexity of Sort Array By Parity?

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

What data structures are used to solve Sort Array By Parity?

This problem uses Array, Two Pointers, Sorting. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Sort Array By Parity?

Insight 1: We need to separate even and odd numbers within the array. Insight 2: A two-pointer approach can be used for an in-place solution, potentially optimizing space complexity.

Which companies ask LeetCode 905. Sort Array By Parity in interviews?

This problem is frequently asked at DXC Technology.

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

Sort Array By Parity - LeetCode 905 Solution

Q: How to solve Sort Array By Parity?

The Python solution utilizes a simple approach of creating two separate lists, one for even numbers and one for odd numbers. It iterates through the input array, appending each number to the appropriate list based on its parity (even or odd). Finally, it concatenates the even list with the odd list and returns the result. The Java and C++ solutions use a two-pointer approach for an in-place modification. The C solution uses a similar approach to the python one allocating a new array and sorting into the array. Both are valid.

Sort Array By Parity - Complete Solution Guide

Sort Array By Parity is LeetCode problem 905, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an integer array nums , move all the even integers at the beginning of the array followed by all the odd integers. Return any array that satisfies this condition . Example 1: Input: nums = [3,1,2,4] Output: [2,4,3,1] Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Example 2: Input: nums = [0] Output: [0] Constraints: 1 <= nums.length <= 5000 0 <= nums[i] <= 5000

Detailed Explanation

The problem asks us to rearrange the elements of an integer array `nums` such that all even integers precede all odd integers. The order among the even numbers or among the odd numbers is not specified, so multiple valid outputs are possible. The input is the integer array `nums`. The output is an integer array with even numbers at the beginning, followed by odd numbers.

Solution Approach

The Python solution utilizes a simple approach of creating two separate lists, one for even numbers and one for odd numbers. It iterates through the input array, appending each number to the appropriate list based on its parity (even or odd). Finally, it concatenates the even list with the odd list and returns the result. The Java and C++ solutions use a two-pointer approach for an in-place modification. The C solution uses a similar approach to the python one allocating a new array and sorting into the array. Both are valid.

Step-by-Step Algorithm

Step 1: Python: Initialize two empty lists, `even` and `odd`. Java/C++: Initialize two pointers, `left` at the beginning of the array and `right` at the end of the array. C: Allocate new array of the same size.
Step 2: Python: Iterate through the input array `nums`. Java/C++: Start a `while` loop that continues as long as `left < right`. C: Iterate through the input array `nums`.
Step 3: Python: For each number, check if it's even (divisible by 2). If it is, append it to the `even` list; otherwise, append it to the `odd` list. Java/C++: If `nums[left]` is odd and `nums[right]` is even, swap them and move both pointers. If `nums[left]` is even, move `left` forward. If `nums[right]` is odd, move `right` backward. C: If the number is even add to the even index and increment it; otherwise add the number to the odd index and decrement it.
Step 4: Python: After iterating through all numbers, concatenate the `even` list with the `odd` list. Java/C++: The array `nums` is now sorted by parity. C: The array is now sorted.
Step 5: Python: Return the concatenated list. Java/C++: Return the modified array `nums`. C: return the new array.

Key Insights

Insight 1: We need to separate even and odd numbers within the array.
Insight 2: A two-pointer approach can be used for an in-place solution, potentially optimizing space complexity.
Insight 3: The problem emphasizes that *any* valid output is acceptable, which relaxes the requirements and allows for simpler solutions.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Two Pointers, Sorting.

Companies

Asked at: DXC Technology.

Sort Array By Parity | LeetCode 905

Easy

Array Two Pointers Sorting

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

Solution Code

Available in:

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int evenIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                int temp = nums[evenIndex];
                nums[evenIndex] = nums[i];
                nums[i] = temp;
                evenIndex++;
            }
        }
        return nums;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 905: Sort Array By Parity - Detailed explanation and solution approaches.

Topics

Array Two Pointers Sorting

Companies

DXC Technology

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:905

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

5 steps

1
Step 1: Python: Initialize two empty lists, `even` and `odd`. Java/C++: Initialize two pointers, `left` at the beginning of the array and `right` at the end of the array. C: Allocate new array of the same size.
2
Step 2: Python: Iterate through the input array `nums`. Java/C++: Start a `while` loop that continues as long as `left < right`. C: Iterate through the input array `nums`.
3
Step 3: Python: For each number, check if it's even (divisible by 2). If it is, append it to the `even` list; otherwise, append it to the `odd` list. Java/C++: If `nums[left]` is odd and `nums[right]` is even, swap them and move both pointers. If `nums[left]` is even, move `left` forward. If `nums[right]` is odd, move `right` backward. C: If the number is even add to the even index and increment it; otherwise add the number to the odd index and decrement it.
4
Step 4: Python: After iterating through all numbers, concatenate the `even` list with the `odd` list. Java/C++: The array `nums` is now sorted by parity. C: The array is now sorted.
5
Step 5: Python: Return the concatenated list. Java/C++: Return the modified array `nums`. C: return the new array.

💡

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 single loop iterating through the array. In Python and C, additional space is used to store the even and odd numbers, leading to O(n) space complexity. Java and C++ perform in-place sorting, so they use only a constant amount of extra space. The C++ solution may have a hidden O(log n) space complexity due to the swap operation's implementation details, but this is often optimized by compilers.

📖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

Using a custom comparator with sorting

Use built-in sorting functions with a custom comparator function that compares numbers based on their parity. Even numbers should come before odd numbers.

Time: O(n log n) because sorting algorithms typically have this time complexity.Space: O(1) or O(n) depending on the sorting algorithm's implementation.

Trade-offs: This approach is simpler to implement using built-in functions but less efficient than the linear-time two-pointer or separate list approach. Suitable when performance is not a primary concern.

✨

Key Insights

1Insight 1: We need to separate even and odd numbers within the array.
2Insight 2: A two-pointer approach can be used for an in-place solution, potentially optimizing space complexity.
3Insight 3: The problem emphasizes that *any* valid output is acceptable, which relaxes the requirements and allows for simpler solutions.

📚

Key Terms Explained

For Students

Array

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

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Empty input array. Both solutions will work correctly because the loop won't execute, returning the original empty array (or a new empty array in the case of C).
Edge case 2: Array with only even or only odd numbers. The Python solution will result in one list being empty and the other containing all the numbers. The Java/C++ solutions will correctly arrange the array. The C solution will return a correctly sorted array.
Edge case 3: Array with duplicate numbers. The solutions will correctly handle this case because the parity check and swapping (or appending) operations work regardless of duplicate values.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the edge case of an empty input array.

✗Common mistake 2: Trying to maintain the original order of even or odd numbers within their respective groups, which is not required by the problem and makes the solution more complex.

✗Common mistake 3: Forgetting to allocate a new array or returning the correct size when creating a new array(C solution).

✅

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 preprocessing in machine learning. You might want to separate features based on whether they are integer or floating-point for different processing steps.

🏦Real-world scenario 2: File organization. Separating files into different directories based on a certain property (e.g., file size being even or odd).

🎮Real-world scenario 3: Task scheduling. Prioritizing tasks based on whether their IDs are even or odd for load balancing.

💡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

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

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

👨‍💻 From Experience

This is one of the first problems I solved when learning Array. It's a great foundation for more complex problems.

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 6, 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

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

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

@InterviewProJun 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.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

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 "Sort Array By Parity"?

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

🤖 Need help with this problem?