Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

Move Zeroes

Array, Two Pointers

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]

Solutions

The problem is asking to move all zeros in the given array to the end while maintaining the relative order of the non-zero elements. This means that the sequence of non-zero numbers in the array should remain the same after all the zeros have been moved to the end.

Approach – Brute Force Technique

In the brute force approach, we use a simple bubble sort algorithm to push the zeros to the end of the array.

Steps

  1. Get the length of the array: The variable n is assigned the length of the nums array.

  2. Outer loop: The outer loop runs from i = 0 to i = n - 1. This loop iterates over each element in the array.

  3. Inner loop: The inner loop runs from j = 0 to j = n - i - 2. This loop compares each element with its next element.

  4. Check for zero: If the current element nums[j] is zero, then it needs to be moved to the end.

  5. Swap elements: If nums[j] is zero, it is swapped with the next element nums[j + 1]. This is done by creating a temporary variable temp to hold the value of nums[j], then assigning nums[j] the value of nums[j + 1], and finally assigning nums[j + 1] the value of temp.

  6. Repeat: The process is repeated for all elements in the array until all zeros have been moved to the end.

public class Solution
{

    public void MoveZeroes(int[] nums)
    {
        int n = nums.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n - i - 1; j++)
            {
                if (nums[j] == 0)
                {
                    // Swap nums[j] and nums[j + 1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

Complexity

  • Time Complexity: O(n^2)

  • Auxiliary Space: O(1)

Approach – Two Pointers Technique

In the optimized approach, we keep track of the last non-zero element found in the array. We then swap the current element with the last non-zero element if the current element is non-zero.

Steps

  1. Initialize a pointer: The variable lastNonZeroFoundAt is initialized to 0. This pointer will keep track of the position where the next non-zero element should be moved.

  2. Iterate through the array: The first for loop runs from i = 0 to i = nums.Length - 1. This loop iterates over each element in the array.

  3. Check if the current element is non-zero: If the current element nums[i] is non-zero, then it needs to be moved to the position pointed by lastNonZeroFoundAt.

  4. Move non-zero elements to the front: If nums[i] is non-zero, it is moved to the position nums[lastNonZeroFoundAt], and then the lastNonZeroFoundAt pointer is incremented. This effectively moves all non-zero elements to the front of the array, while maintaining their relative order.

  5. Fill the rest of the array with zeros: The second for loop runs from i = lastNonZeroFoundAt to i = nums.Length - 1. This loop sets all the remaining elements in the array to zero.

public class Solution
{
 
    public void MoveZeroes(int[] nums)
    {
        int lastNonZeroFoundAt = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] != 0)
            {
                nums[lastNonZeroFoundAt++] = nums[i];
            }
        }
        for (int i = lastNonZeroFoundAt; i < nums.Length; i++)
        {
            nums[i] = 0;
        }
    }
}

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(1)

PreviousHouse RobberNextRotate Array

Last updated 1 year ago