Python Program to Rearrange the array in alternating positive and negative items with O(1) extra space
Rearrange the array in Python
Here, on this page will learn how to solve Rearrange the array in alternating positive and negative items with O(1) extra space in Python programing language. In O(n) time complexity.
Example:
- Input : [ 7, 5, -2, 1, -3 ]
- Output : [ -2, 5, -3, 1, 7 ]
Algorithm
- Initialize two variable p, b with value 0
- Run a for loop from 0 to length of array using variable i
- For each iteration if b is equals to 1 then make b equals to -1
- else if arr[i] is less then zero
- Swap values of arr[i] & arr[p]
- If p is greater then i increment the value of b by 1
- Increment value of p by 2
- After loop ends print arr
Time And Space Complexity :
- Time – Complexity : O(N)
- Space – Complexity : O(1)
Run
def rearrange(arr):
p = 0
b = 0
for i in range(len(arr)):
if b == 1:
b -= 1
elif arr[i] < 0:
arr[i], arr[p] = arr[p], arr[i]
if p > i:
b += 1
p += 2
return arr
array = [2, 3, -4, -1, 6, -9]
print("After Rearranging :", rearrange(array))
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
For similar Question click on given button.
Login/Signup to comment
def rearrange_array_in_alternating_positive_and_negative_items(arr):
n = len(arr)
i, j = 0, n-1
while (i<j):
while (i 0):
i += 1
while (j >= 0 and arr[j] < 0):
j -= 1
if (i < j):
arr[i], arr[j] = arr[j], arr[i]
if i ==0 and i == n:
return
k = 0
while i < n and k < n:
arr[i], arr[k] = arr[k], arr[i]
i += 1
k += 2
return arr
arr = [2, 7, 8, -3, -17, -4, -6, -5]
print(rearrange_array_in_alternating_positive_and_negative_items(arr))
a=[2, 3, -4, -1, 6, -9]
p=0
for i in range(0,len(a)):
if a[i]<0:
a[p],a[i]=a[i],a[p]
p+=2
print(a)
Kindly refer to our discord community for all your technical doubts.