3233343536373839404142434445

package main

import (
    "fmt"
)

func rearrangeArray(nums []int) []int {
    n := len(nums)

    // Define 2 slices, one for storing positive
    // and the other for negative elements of the array
    pos := []int{}
    neg := []int{}

    // Segregate the array into positives and negatives
    for i := 0; i < n; i++ {
        if nums[i] > 0 {
            pos = append(pos, nums[i])
        } else {
            neg = append(neg, nums[i])
        }
    }

    // Positives on even indices, negatives on odd
    for i := 0; i < n/2; i++ {
        nums[2*i] = pos[i]
        nums[2*i+1] = neg[i]
    }

    // Return the result
    return nums
}

func main() {
    A := []int{1, 2, -4, -5}

    // Get the rearranged slice
    ans := rearrangeArray(A)

    // Print the result
    for _, num := range ans {
        fmt.Print(num, " ")
    }
}

Complexity Analysis:

Time Complexity: O(N+N/2), where N is the size of the array. O(N) for traversing the array once for segregating positives and negatives and another O(N/2) for adding those elements alternatively to the array.

Space Complexity: O(N/2 + N/2) = O(N), N/2 space required to store each of the positive and negative elements in separate arrays.1d:T4bc7,

Intuition

Consider having a group of kids, and you need them to line up for a photo such that they alternate between wearing red shirts and blue shirts, and the line starts with a red shirt. Let's say there are equal numbers of kids wearing red and blue shirts.

Begin with the first position designated for a kid wearing a red shirt. The second position is for a kid wearing a blue shirt.

After calling out the kids, place the first red shirt kid at the first position. Then place the first blue shirt kid at the second position. Continue this process, placing each subsequent red shirt kid at the next available "red" position, and each blue shirt kid at the next available "blue" position.

Approach

Initialize two variable posIndex as 0 and negIndex as 1 initially.

Now, iterate in the array & on encountering the first negative element, understand that its first position in resultant array should be starting from index 1, as initially positive number will be placed. And then each time when a negative number is found, its next position would be 2 steps ahead considering that a positive number will occupy space in between 2 negative numbers. So increment the position of negative number by 2.

Similarly, when you encounter the first positive element, it occupies the position at index 0 in the resultant array, and then each time on finding a positive number, put it on the posIndex and it increments by 2.

When both the negIndex and posIndex exceed the size of the array, stop the iteration as the whole array is now rearranged alternatively according to the sign.

Dry Run