# 14.02.2024 [2149. Rearrange Array Elements by Sign]
Rearrange array to positive-negative sequence.
14.02.2024
2149. Rearrange Array Elements by Sign medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/505
Problem TLDR
Rearrange array to positive-negative sequence.
Intuition
First is to understand that we can’t do this in-place: for example 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1
we must store somewhere the 1
s that is changed by -1
s.
Next, just use two pointers and a separate result array.
Approach
We can use ping-pong technique for pointers and make work with only the current pointer.
Some language’s APIs:
Kotlin:
indexOfFirst
,also
,find
Rust:
iter
,position
,find
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun rearrangeArray(nums: IntArray): IntArray {
var i = nums.indexOfFirst { it > 0 }
var j = nums.indexOfFirst { it < 0 }
return IntArray(nums.size) {
nums[i].also { n ->
i = (i + 1..<nums.size)
.find { n > 0 == nums[it] > 0 } ?: 0
i = j.also { j = i }
}
}
}
pub fn rearrange_array(nums: Vec<i32>) -> Vec<i32> {
let mut i = nums.iter().position(|&n| n > 0).unwrap();
let mut j = nums.iter().position(|&n| n < 0).unwrap();
(0..nums.len()).map(|_| {
let n = nums[i];
i = (i + 1..nums.len())
.find(|&i| (n > 0) == (nums[i] > 0)).unwrap_or(0);
(i, j) = (j, i); n
}).collect()
}