Rearrange Array Elements by Sign

Introduction

Today, I tackled a LeetCode daily challenge problem with a medium difficulty level: Rearrange Array with Alternating Signs. The task involves rearranging an array to ensure that every consecutive pair of integers has opposite signs, while maintaining the order of positive and negative integers as they appeared in the original array. This problem involves array manipulation, two pointers, and simulation techniques. Let’s dive into the problem statement, approach, and solution.

Problem Statement

You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers. You need to rearrange the array such that:

1. Every consecutive pair of integers has opposite signs.

2. The order of integers with the same sign is preserved.

3. The rearranged array begins with a positive integer.

Example 1:

Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4]

Example 2:

Input: nums = [-1,1] Output: [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.

Approach to Solve the Problem

To solve this problem, we can use two pointers to keep track of the positions for positive and negative integers and place them alternately in a new array. Here are the steps involved:

1. Initialize Pointers and Result Array: Use two pointers i and j to track positions for positive and negative integers respectively, and initialize a result array of the same length as nums.

2. Traverse Original Array: Iterate through the original array and place positive integers at even indices and negative integers at odd indices in the result array.

3. Increment Pointers: Increment the pointers by 2 after placing each positive or negative integer to ensure alternating positions.

Solution

Here’s the Java code that implements the above approach:

public int[] rearrangeArray(int[] nums) {
    int n  = nums.length;

    int i = 0;
    int j = 1;

    int [] ans = new int[n];

    for(int k = 0; k < n; k++){
        if(nums[k] > 0){
            ans[i] = nums[k];
            i += 2;
        }
        else{
            ans[j] = nums[k];
            j += 2;
        }
    }

    return ans;
}

Explanation

1. Initialization: The pointers i and j are initialized to 0 and 1 respectively to place positive integers at even indices and negative integers at odd indices.

2. Traverse and Place: The for loop traverses the original array, and positive integers are placed at the positions pointed by i while negative integers are placed at the positions pointed by j.

3. Increment Pointers: After placing each integer, the respective pointer is incremented by 2 to maintain the alternating pattern.

Performance

This solution is efficient with a time complexity of O(n), where n is the length of the array. It performs the rearrangement in a single pass through the array.

Conclusion

This problem reinforces the importance of array manipulation and the efficient use of pointers to solve rearrangement problems. The approach ensures that the conditions are met while maintaining the original order of positive and negative integers.

I hope you found this explanation helpful. Stay tuned for more daily blogs on interesting problems and concepts I encounter in my learning journey!