Move All Negative Elements to End1813

Summary

Move all negative elements to end is a classic array manipulation problem. Given an array of integers, we need to rearrange its elements such that all negative numbers come last in the array while maintaining their original order among themselves and with non-negative numbers.

Detailed Explanation

To solve this problem, we can use a two-pointer approach. We maintain two pointers, i and j, both initialized to 0. The pointer i points to the current element being processed, and the pointer j points to the position where the next non-negative number should be placed.

Here's the step-by-step breakdown of the solution:

Initialize i and j to 0.
Iterate through the array:
- If the current element at index i is negative, increment i.
- If the current element at index i is non-negative, swap it with the element at index j, then increment both i and j.
Continue iterating until all elements have been processed.

Time complexity: O(n), where n is the length of the array. Space complexity: O(1), as we only use a few extra variables to store the pointers.

Optimized Solutions

Java

public static void moveAllNegativeElementsToEnd(int[] arr) { int i = 0, j = 0; while (j < arr.length) { if (arr[j] < 0) { i++; } else { swap(arr, i, j); i++; } j++; } for (int k = i; k < arr.length; k++) { arr[k] *= -1; } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }