MediumCoding

Rearrange array elements by sign

Asked at

Expedia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an integer array **nums of even length consisting of an equal number of positive and negative **integers.Return the answer array in such a way that the given conditions are met:

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.

Input : nums = [2, 4, 5, -1, -3, -4] **Output **: [2, -1, 4, -3, 5, -4] Explanation: The positive number 2, 4, 5 maintain their relative positions and -1, -3, -4 maintain their relative positions

**Input **: nums = [1, -1, -3, -4, 2, 3] **Output **: [1, -1, 2, -3, 3, -4] Explanation: The positive number 1, 2, 3 maintain their relative positions and -1, -3, -4 maintain their relative positions

Input: nums = [-4, 4, -4, 4, -4, 4]

2 <= nums.length <= 105
1 <= | nums[i] | <= 104
nums.length is an even number.
Number of positive and negative numbers are equal.

cpp

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        
    }
};

java

class Solution {
    public int[] rearrangeArray(int[] nums) {
        
    }
}

python

class Solution:
    def rearrangeArray(self, nums):

javascript

class Solution {
    rearrangeArray(nums) {

    }
}

csharp

public class Solution {
    public int[] RearrangeArray(int[] nums) {
        // Write your code here
    }
}

func rearrangeArray(nums []int) []int {
	//your code goes here
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Clarify count guarantee
02Allocate result or use positions
03Place positives at even indexes
04Place negatives at odd indexes
05State complexity

Reference answer

Use two output positions

With equal counts and an output beginning positive, allocate a result array, keep positiveIndex = 0 and negativeIndex = 1, and scan the input once. Put each positive at the next even position and each negative at the next odd position, advancing that position by two. Because each sign is encountered in original order, relative order within each sign is preserved. Runtime is O(n) and extra space is O(n). If the prompt requires in-place work or unequal counts, clarify it: the usual LeetCode contract is different from the variant that appends leftover values after alternation. Test all legal smallest inputs, alternating input, grouped signs, zeros if zero's sign is specified, and the first sign requirement. Do not assume an unstable partition preserves order.

Then expect these follow-ups

Why is relative order preserved?
Tests: correctness reasoning
How changes when counts are unequal?
Tests: constraint adaptation

Hiring now

Expedia has 109 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III - Platform Productivity Tools
India - Gurgaon
Sr Manager, Software Engineering
Austin Domain 11 - HomeAway
Software Development Engineer II
India - Gurgaon

Or practice this question first

Next question