Reorganize The Array

JavaView on GFG

Intuition

Rearrange array so all negative elements appear before positive. Maintain relative order (stable).

Algorithm

1Two passes: collect negatives maintaining order, then positives. Concatenate.

Common Pitfalls

•Stable partition. O(n) with extra space. In-place stable partition is O(n log n).

Reorganize The Array.java

Java

// Approach: Sort, then split at midpoint and interleave elements from both halves.
// Time: O(n log n) Space: O(n)
class Solution {
    public List<Integer> rearrange(List<Integer> arr) {
        int n = arr.size();
        List<Integer> ans = new ArrayList<Integer>();

        for (int i = 0; i < arr.size(); i++)
            ans.add(-1);

        for (int ele : arr) {
            if (ele >= 0 && ele < arr.size())
                ans.set(ele, ele);
        }

        return ans;
    }
}

Was this solution helpful?