What is the time complexity of Move Zeroes?

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

What data structures are used to solve Move Zeroes?

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

What are the key insights for solving Move Zeroes?

Insight 1: We can use a two-pointer approach or a single pointer to efficiently track the position of the next non-zero element. Insight 2: The problem can be solved in-place without using extra space beyond a few constant variables.

Which companies ask LeetCode 283. Move Zeroes in interviews?

This problem is frequently asked at Agoda, Anduril, BNY Mellon, CEDCOSS, Capgemini and 21 more companies.

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

Move Zeroes - LeetCode 283 Solution

Q: How to solve Move Zeroes?

The provided solutions use a two-pointer approach (in Python) or a single pointer approach (in Java, C++, and C). The single-pointer approach iterates through the array. When a non-zero element is encountered, it's placed at the beginning of a 'non-zero' subarray. This subarray expands as more non-zero numbers are found. Afterwards, the remaining elements are filled with zeros.

Move Zeroes - Complete Solution Guide

Move Zeroes is LeetCode problem 283, 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 0 's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array. Example 1: Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0] Example 2: Input: nums = [0] Output: [0] Constraints: 1 <= nums.length <= 10 4 -2 31 <= nums[i] <= 2 31 - 1 Follow up: Could you minimize the total number of operations done?

Detailed Explanation

The problem asks you to rearrange the elements of an integer array in place. The goal is to move all the zeros to the end of the array while preserving the relative order of the non-zero elements. For example, if the input array is `[0, 1, 0, 3, 12]`, the output should be `[1, 3, 12, 0, 0]`. The crucial constraint is that you cannot create a new array; you must modify the original array directly.

Solution Approach

The provided solutions use a two-pointer approach (in Python) or a single pointer approach (in Java, C++, and C). The single-pointer approach iterates through the array. When a non-zero element is encountered, it's placed at the beginning of a 'non-zero' subarray. This subarray expands as more non-zero numbers are found. Afterwards, the remaining elements are filled with zeros.

Step-by-Step Algorithm

Step 1: Initialize a pointer (or counter) `k` to 0. This pointer will track the index of the next position to place a non-zero element.
Step 2: Iterate through the input array `nums`. If an element `nums[i]` is not zero, copy it to `nums[k]` and increment `k`.
Step 3: After the first loop, all non-zero elements are placed at the beginning of the array (from index 0 to `k-1`).
Step 4: Iterate from `k` to the end of the array and set all elements to 0.

Key Insights

Insight 1: We can use a two-pointer approach or a single pointer to efficiently track the position of the next non-zero element.
Insight 2: The problem can be solved in-place without using extra space beyond a few constant variables.
Insight 3: Optimizing the solution involves minimizing the number of array element swaps or assignments. Avoid unnecessary iterations.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers.

Companies

Asked at: Agoda, Anduril, BNY Mellon, CEDCOSS, Capgemini, Cisco, Cognizant, CrowdStrike, DevRev, Infosys, Intuit, NetApp, Nvidia, Ozon, SAP, Salesforce, ServiceNow, Tesla, VK, Walmart Labs, Wix, Yandex, Zoho, eBay, josh technology, tcs.

Move Zeroes | LeetCode 283

Easy

Array Two Pointers

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

Solution Code

Available in:

class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[k++] = nums[i];
            }
        }
        for (int i = k; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 283: Move Zeroes - Detailed explanation and solution approaches.

Topics

Array Two Pointers

Companies

AgodaAndurilBNY MellonCEDCOSSCapgeminiCiscoCognizantCrowdStrike

Stats

Difficulty:Easy

Languages:4

Companies:26

Problem #:283

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

4 steps

1
Step 1: Initialize a pointer (or counter) `k` to 0. This pointer will track the index of the next position to place a non-zero element.
2
Step 2: Iterate through the input array `nums`. If an element `nums[i]` is not zero, copy it to `nums[k]` and increment `k`.
3
Step 3: After the first loop, all non-zero elements are placed at the beginning of the array (from index 0 to `k-1`).
4
Step 4: Iterate from `k` to the end of the array and set all elements to 0.

💡

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(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array once in each loop (steps 2 and 4), making the time complexity linear with respect to the input array's size. The space complexity is constant because only a few integer variables are used; no additional data structures that scale with the input size are needed.

📖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

Two-Pointer Approach (Python's Solution)

Maintains two pointers. One iterates through the array, and the other points to the next available position for a non-zero element. Swaps elements if necessary.

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

Trade-offs: This approach might be slightly less efficient than the single-pointer approach because it involves more swaps.

✨

Key Insights

1Insight 1: We can use a two-pointer approach or a single pointer to efficiently track the position of the next non-zero element.
2Insight 2: The problem can be solved in-place without using extra space beyond a few constant variables.
3Insight 3: Optimizing the solution involves minimizing the number of array element swaps or assignments. Avoid unnecessary iterations.

📚

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.

Edge Cases

Edge case 1: An array containing only zeros. The solution correctly handles this by leaving the array unchanged.
Edge case 2: An array containing no zeros. The solution correctly handles this by leaving the array unchanged.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Creating a new array to store the result. This violates the in-place requirement of the problem.

✗Common mistake 2: Not maintaining the relative order of non-zero elements. The solution must ensure that the order of non-zero numbers remains the same after the rearrangement.

✅

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 cleaning and preprocessing. In many data processing tasks, you might need to handle missing values (represented by zeros in this case) and rearrange the data for efficient processing.

🏦Real-world scenario 2: Memory management. In some memory allocation systems, zeros might represent free space. Rearranging memory blocks to consolidate free space might involve a similar algorithm.

💡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

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ 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: September 12, 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

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

@CodeNinjaJul 13

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

@TechLeadJul 6

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

@DevExpert92Jun 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 "Move Zeroes"?

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?