Move all Negative Elements to End - CA09

My Thinking and Approach

---

Introduction

In this problem, I was given an array containing both positive and negative integers and asked to move all negative elements to the end.

The important condition is that the relative order of positive and negative elements should not be changed.

---

Problem Statement

• Given an array arr containing:

  • Positive numbers
  • Negative numbers

• Move all negative elements to the end

• Conditions:

  • Maintain order of elements
  • Perform operation in-place

---

My Initial Thought

At first, I considered:

• Creating two separate lists

  • One for positive elements
  • One for negative elements

• Then combining them

But this approach uses extra space.

---

Key Observation

To maintain order:

• I should first place all positive elements
• Then place all negative elements

---

Optimized Approach

I decided to:

• Use an additional list to store elements in order
• Copy elements back to original array

Logic:

• Traverse array
• Add positive elements first
• Add negative elements next
• Copy back to original array

---

My Approach (Step-by-Step)

1. Create an empty list result
2. Traverse array:

• If element is positive → add to result

  1. Traverse again:

• If element is negative → add to result

  1. Copy result back to original array

---

Code (Python)

Below is the implementation clearly separated inside a code block:

def moveNegatives(arr):
    result = []

    for num in arr:
        if num >= 0:
            result.append(num)

    for num in arr:
        if num < 0:
            result.append(num)

    for i in range(len(arr)):
        arr[i] = result[i]

---

Example Walkthrough

Input:

arr = [1, -1, 3, 2, -7, -5, 11, 6]

Steps:

• Positive elements → [1, 3, 2, 11, 6]
• Negative elements → [-1, -7, -5]
• Combine → [1, 3, 2, 11, 6, -1, -7, -5]

Output:

[1, 3, 2, 11, 6, -1, -7, -5]

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

---

Key Takeaways

• Maintaining order is important
• Simple traversal can solve the problem
• Extra space can simplify implementation

---

Conclusion

This problem helped me understand how to rearrange elements while maintaining order.

Even though an in-place solution is preferred, using extra space can make the solution easier to implement.

---