MOVE ZEROES TO END

 

Move Zeroes to End – Two Pointer Approach

Introduction

In this problem, we are given an array and need to move all the zeroes to the end while maintaining the relative order of non-zero elements.

The important constraint is that the operation must be done in-place, without using extra space.

Problem Statement

Given an array nums[], move all 0’s to the end while:

  • Maintaining the order of non-zero elements

  • Not using extra space

Example

Input:

nums = [0, 1, 0, 3, 12]

Output:

[1, 3, 12, 0, 0]

Solution Code

class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0; // position for next non-zero element

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }
}

Approach Used: Two Pointer Technique

Idea

We use two pointers:

  • i = scans the array

  • j = keeps track of where the next non-zero element should go

How It Works

  1. Initialize j = 0

  2. Traverse array using i

  3. If nums[i] is not zero:

    • Swap nums[i] with nums[j]

    • Increment j

  4. Continue until the end

Why This Approach Was Chosen

  • Works in one pass (O(n))

  • Maintains relative order of non-zero elements

  • Uses constant space (O(1))

  • Efficient and simple logic

Alternative Approaches

  • Using extra array
    Copy non-zero elements first, then add zeros
     Uses extra space

  • Shift elements manually
     More complex and less efficient

Why Two Pointer?
Because it satisfies both constraints:

  • In-place

  • Maintains order

Time and Space Complexity

  • Time Complexity: O(n)

  • Space Complexity: O(1)

Important Observation

  • Swapping ensures non-zero elements move forward

  • Zeroes automatically move to the end

  • Order of non-zero elements remains unchanged

Conclusion

The two-pointer approach provides an efficient and clean solution to move zeroes to the end of the array. It satisfies all constraints by working in-place and maintaining order, making it the optimal choice for this problem.

Comments

Post a Comment

Popular posts from this blog

THE DELIVERY MAN

  The Delivery Man – Python List Operations  Introduction Lists in Python are used to store multiple items in a single variable. They are flexible, allowing us to add, remove, update, and manipulate elements easily. In this task, different list operations are performed to simulate a delivery man's workflow. 1. Creating a list and accessing an item items = ["Notebook", "Pencil", "Eraser", "Ruler", "Marker"] print(items[2]) Approach: Indexing Why: Lists use zero-based indexing, so the third item is accessed using index 2. 2. Adding a new item items.append("Glue Stick") print(items) Approach: append() method Why: It adds an item at the end of the list, which is ideal for adding new deliveries. 3. Inserting an item items.insert(2, "Highlighter") print(items) Approach: insert() method Why: Used when we need to add an item at a specific position instead of the end. 4. Removing an item items.remove("Ruler...
Read more

EC2 LAUNCHING

  EC2 Step 1: Launch EC2 Instance Go to: AWS Console --> EC2 --> Launch Instance Configure: Name : my-web-server AMI : Amazon Linux 2 (easy for beginners) Instance Type : t2.micro (free tier) Step 2: Key Pair Create or select a key pair. Step 3: Network Settings  Allow these: SSH (port 22) --> for login  HTTP (port 80) --> for web access Step 4: Launch Instance Click Launch Instance Step 5: Connect to Instance Use: EC2 --> Connect --> EC2 Instance Connect (easiest) OR via terminal: with this command. for this you have to download the pem files while selecting the key pair.  ssh -i your-key.pem ec2-user@<public-ip> Step 6: Install Web Server For Amazon Linux: sudo yum update -y sudo yum install httpd -y Step 7: Start Web Server sudo systemctl start httpd sudo systemctl enable httpd Step 8: Add a Web Page echo "Hello from EC2" | sudo tee /var/www/html/index.html Step 9: Get Public IP Go to EC2 d...
Read more

SORT A LINKED LIST USING MERGE SORT

  Sort a Linked List using Merge Sort Introduction Sorting a linked list efficiently is a common problem in data structures. Unlike arrays, linked lists do not allow direct access to elements, so algorithms like quicksort are not ideal. Merge Sort is the best choice for linked lists because: It does not require random access It works efficiently with node-based structures Problem Statement Given the head of a linked list: Sort the list in ascending order Return the sorted linked list Example Input: 10 -> 30 -> 20 -> 40 -> 60 -> 50 Output: 10 -> 20 -> 30 -> 40 -> 50 -> 60 Solution Code class Solution: def mergeSort(self, head): if not head or not head.next: return head mid = self.getMiddle(head) next_to_mid = mid.next mid.next = None left = self.mergeSort(head) right = self.mergeSort(next_to_mid) return self.merge(left, right) def getMiddle(self,...
Read more