Move all negative elements at the end of array
The problem is to move all negative elements to the end of the array while maintaining the relative order of positive elements. The goal is to rearrange the elements of the array in such a way that all negative elements come after all positive elements. The relative order of positive elements within the sorted array should be the same as in the original array.
Example
Consider the following array:
[1, -1, 3, 2, -7, -5, 11, 6]
After rearranging, the array becomes:
[1, 6, 3, 2, 11, -5, -7, -1]
All negative elements have been moved to the end of the array while preserving the order of positive elements.
Idea to Solve the Problem
To solve this problem, we can use a two-pointer approach. We maintain two pointers, i
and
j
, where i
starts from the beginning of the array and j
starts from the
end of the array. We move i
from left to right and j
from right to left. At each step,
we check if the element at i
is negative and the element at j
is positive. If so, we
swap these elements to move the negative element to the end of the array. We repeat this process until
i
becomes greater than or equal to j
.
Algorithm
- Initialize two pointers,
i
andj
, wherei
starts from the beginning of the array (index 0) andj
starts from the end of the array (indexn - 1
, wheren
is the size of the array). - Repeat the following steps until
i
becomes greater than or equal toj
: a. If the element at indexi
is negative and the element at indexj
is positive, swap these elements. b. If the element at indexi
is positive, incrementi
. c. If the element at indexj
is negative, decrementj
. - After the loop, all negative elements will be moved to the end of the array.
Pseudocode
function moveNegative(arr):
i = 0
j = size of arr - 1
while i < j:
if arr[i] < 0 and arr[j] >= 0:
swap arr[i] with arr[j]
increment i
decrement j
else if arr[i] >= 0:
increment i
else:
decrement j
end function
Code Solution
-
1) Move all negative elements to end in java
2) Move all negative elements to end in c++
3) Move all negative elements to end in c
4) Move all negative elements to end in c#
5) Move all negative elements to end in golang
6) Move all negative elements to end in node js
7) Move all negative elements to end in python
8) Move all negative elements to end in ruby
9) Move all negative elements to end in php
10) Move all negative elements to end in scala
11) Move all negative elements to end in swift
12) Move all negative elements to end in kotlin
13) Move all negative elements to end in vb.net
14) Move all negative elements to end in typescript
Time Complexity
- The above algorithm has a time complexity of O(N), where N is the number of elements in the array. This is because we traverse the array once and perform constant-time swap or increment/decrement operations for each element.
- Therefore, the algorithm is efficient for moving negative elements to the end of an array with a large number of elements.
Resultant Output Explanation
The given program implements the algorithm to move negative elements to the end of the array while preserving the relative order of positive elements.
In the provided output, the program displays the initial array elements before rearranging and the array elements after rearranging. The algorithm moves all negative elements to the end of the array while maintaining the order of positive elements.
The output shows the sorted array, where all negative elements come after all positive elements, and the relative order of positive elements within the array remains the same as in the original array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment