Move All Negative Elements to End

Source: Dev.to

---

⚠️ Collection Error: Content refinement error: Error: 429 429 Too Many Requests: you (bkperio) have reached your weekly usage limit, upgrade for higher limits: https://ollama.com/upgrade

---

Problem Statement

Given an array arr[] containing both positive and negative integers, move all negative elements to the end of the array without changing the relative order of elements. At first, I thought this is similar to partitioning (like quicksort or two-pointer problems). The order of elements must not change. This changes the entire approach. If I try swapping elements (like placing negatives at the end using two pointers), the order of positive elements or negative elements may get disturbed. So I needed a way to rearrange elements while keeping their original sequence intact. We are not asked to sort. Keep all non-negative elements in the front (in the same order) Move all negative elements to the end (in the same order) This means the solution must be stable. To maintain order, I used an extra array. This helps us rebuild the array without disturbing order. Traverse the array and copy all elements >= 0 into the temporary array. This ensures: All positive and zero values come first Their order remains unchanged Traverse the array again and copy all elements = 0) { temp[index++] = arr[i]; } }

    // Step 2: add negative elements
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            temp[index++] = arr[i];
        }
    }

    // Step 3: copy back
    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}

}

Time Complexity: O(n) Space Complexity: O(n) We are not disturbing the order of elements We are simply reconstructing the array in two phases This guarantees a stable result Whenever a problem includes a constraint like: “Do not change the order” Avoid swapping-based solutions and think about stable rearrangement using extra space.