Teaching Kids Programming – Rearrange Array Elements by Sign (Two Pointer Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers. You should rearrange the elements of nums such that the modified array follows the given conditions:

Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:
Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.

Example 2:
Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Constraints:
2 <= nums.length <= 2 * 10^5
nums.length is even
1 <= |nums[i]| <= 10^5
nums consists of equal number of positive and negative integers.

Hints:
Divide the array into two parts- one comprising of only positive integers and the other of negative integers.
Merge the two parts to get the resultant array.

Two Pointer Algorithm to Rearrange Array by Sign

We can keep two pointers one for storing the positive numbers, and the other for negative numbers. Once a number is filled in the corresponding position, the corresponding pointer needs to move two space ahead. We can directly modify the original number since the numbers may be lost due to overwritten.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pa = 0
        na = 1
        data = nums[:]
        for j in nums:
            if j > 0:
                data[pa] = j
                pa += 2
            else:
                data[na] = j
                na += 2
        return data     

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pa = 0
        na = 1
        data = nums[:]
        for j in nums:
            if j > 0:
                data[pa] = j
                pa += 2
            else:
                data[na] = j
                na += 2
        return data     

The time complexity is O(N) i.e. iterate the array once, and the space complexity is O(N) as we need to store numbers in a separate array.

We can divide the original array into two, one for positives, and other for negatives, and then we can zip two arrays and take them one by one.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = [x for x in nums if x > 0]
        neg = [x for x in nums if x < 0]
        ans = []
        for x in zip(pos, neg):
            # we can append them one by one
            # ans.extend(x[0]); ans.extend(x[1])
            ans.extend([x[0], x[1]])  # or ans.extend(list(x))
        return ans

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = [x for x in nums if x > 0]
        neg = [x for x in nums if x < 0]
        ans = []
        for x in zip(pos, neg):
            # we can append them one by one
            # ans.extend(x[0]); ans.extend(x[1])
            ans.extend([x[0], x[1]])  # or ans.extend(list(x))
        return ans

We can use the list comprehension to assign the positives and negatives:

1
2
3
4
5
6

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = [x for x in nums if x > 0]
        neg = [x for x in nums if x < 0]
        nums[0::2], nums[1::2] = pos, neg
        return nums        

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = [x for x in nums if x > 0]
        neg = [x for x in nums if x < 0]
        nums[0::2], nums[1::2] = pos, neg
        return nums        

The Python List Comprehension namely, arr[i:j:k] means the slicing of array start at index i, ends at index j (excluding) and step is k (non-zero). [::-1] is the reverse. By default, i=0, j=len(arr) and k=1.

This implementation is concise and pretty.

–EOF (The Ultimate Computing & Technology Blog) —