Skip to content

Latest commit

 

History

History
142 lines (106 loc) · 3.36 KB

Day 2 - Move All Zeroes to End.md

File metadata and controls

142 lines (106 loc) · 3.36 KB
Difficulty Source Tags
Easy
160 Days of Problem Solving
Arrays

🚀 Day 2. Move All Zeroes to End 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description:

Given an array arr[], move all the zeros in the array to the end while maintaining the relative order of non-zero elements. The modification should be done in-place.

🔍 Example Walkthrough:

Input:

arr[] = [1, 2, 0, 4, 3, 0, 5, 0]

Output:

[1, 2, 4, 3, 5, 0, 0, 0]

Explanation:
The three zeros are moved to the end while the relative order of non-zero elements is maintained.

Input:

arr[] = [10, 20, 30]

Output:

[10, 20, 30]

Explanation:
No change in the array as there are no zeros.

Input:

arr[] = [0, 0]

Output:

[0, 0]

Explanation:
No change in the array as all elements are zeros.

🎯 My Approach:

  1. Two-Pointer Technique:

    • Use a pointer nonZeroIndex to track the position where the next non-zero element should be placed.
    • Traverse the array, and whenever a non-zero element is encountered, swap it with the element at the nonZeroIndex and increment the pointer.
    • This ensures all non-zero elements are shifted to the front, and zeros naturally move to the end.
  2. Edge Cases:

    • If the array contains no zeros, return the array as is.
    • If the array contains only zeros, no changes are needed.

🕒 Time and Auxiliary Space Complexity📝

  • Expected Time Complexity: O(n), where n is the number of elements in the array. Each element is traversed once to determine its position.
  • Expected Auxiliary Space Complexity: O(1), as no additional space is used apart from a few variables.

📝 Solution Code

Code (C++)

class Solution {
public:
    void pushZerosToEnd(std::vector<int>& arr) {
        int n = arr.size();
        int nonZeroIndex = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] != 0) {
                std::swap(arr[nonZeroIndex++], arr[i]);
            }
        }
    }
};

Code (Java)

class Solution {
    void pushZerosToEnd(int[] arr) {
        int n = arr.length;
        int nonZeroIndex = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] != 0) {
                int temp = arr[nonZeroIndex];
                arr[nonZeroIndex] = arr[i];
                arr[i] = temp;
                nonZeroIndex++;
            }
        }
    }
}

Code (Python)

class Solution:
    def pushZerosToEnd(self, arr):
        n = len(arr)
        nonZeroIndex = 0

        for i in range(n):
            if arr[i] != 0:
                arr[nonZeroIndex], arr[i] = arr[i], arr[nonZeroIndex]
                nonZeroIndex += 1

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐


📍Visitor Count