LeetCode Entry
2149. Rearrange Array Elements by Sign
Rearrange array to positive-negative sequence.
2149. Rearrange Array Elements by Sign medium
blog post
substack
youtube
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 1s that is changed by -1s.
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()
}