Rearrange Array Elements By Sign - Leetcode Solution

Problem Statement: Given an array of integers, rearrange the array such that all the negative numbers come before all the positive numbers, maintaining the order of their occurrence.

Example: Input: [-1, 2, -3, 4, 5, -6, -7, 8, -9] Output: [-1, -3, -6, -7, -9, 2, 4, 5, 8]

Explanation: In this example, all the negative numbers, i.e., [-1, -3, -6, -7, -9] are placed before all the positive numbers [2, 4, 5, 8]. The order of occurrence is also maintained.

Solution: The problem can be solved by using a two-pointer approach. We can use one pointer (i) to traverse the array from left to right to find negative numbers. At the same time, we can use another pointer (j) to traverse the array from left to right to find positive numbers. Whenever we find a negative number, we swap it with the next positive number that we find.

Algorithm:

1. Initialize two pointers i and j to point to the first element of the array.
2. While i is less than the length of the array, a. If the ith element is negative, do nothing. b. If the ith element is positive, then traverse the array from j to i. c. If a positive element is found at index k, swap the ith and kth element. d. Increment j by 1 to continue searching for positive elements.
3. Return the rearranged array.

Python Code:

def rearrange(arr): n = len(arr) i = 0 j = 0 while i < n: if arr[i] < 0: i += 1 else: j = i + 1 while j < n: if arr[j] >= 0: j += 1 else: arr[i], arr[j] = arr[j], arr[i] i += 1 break else: break return arr

arr = [-1, 2, -3, 4, 5, -6, -7, 8, -9] print(rearrange(arr)) # [-1, -3, -6, -7, -9, 2, 4, 5, 8]

Time Complexity: O(N^2), where N is the length of the array. In the worst-case scenario, we may traverse the array twice for each element. Space Complexity: O(1), since we are performing the rearrangement in-place.

1