When working with arrays, a common problem is to rearrange elements based on a condition while keeping their original order intact. In this case, the task is to move all negative numbers to the end of the array while keeping the order of both positive and negative numbers the same as in the original array. This is important because simply swapping elements may disturb the order, which is not allowed here.
A straightforward idea is to scan the array and whenever a positive number is found, shift it toward the front. This approach maintains the order but involves repeatedly shifting elements, which makes it slow for large inputs. Its time complexity becomes quadratic, which is why it fails in cases with large data and results in a time limit exceeded error.
To solve this efficiently, a better approach is to use an additional array. First, traverse the original array and copy all positive elements into the new array in the same order. Then, traverse the array again and copy all negative elements into the new array, again maintaining their order. Finally, copy the elements from the new array back into the original array. This approach ensures that the relative order of elements is preserved and runs in linear time.
Although this method uses extra space, it is the most practical solution for this problem because it avoids unnecessary shifting and improves performance significantly. In many real coding platforms, this is the expected approach when both stability and efficiency are required.
Top comments (0)