Lecture 47 :- Move All Negative Number To The Left Side of an Array

To move all negative numbers to the left side of an array, you can use the Two-Pointer technique. The idea is to maintain two pointers, one at the beginning of the array (left pointer) and another at the end of the array (right pointer). The left pointer will move towards the right, and the right pointer will move towards the left until they meet.

Here's the algorithm to achieve this:

1. Initialize two pointers left and right, where left is set to the beginning of the array (index 0), and right is set to the end of the array (index n-1, where n is the size of the array).
2. Repeat the following until left is less than or equal to right: a. If the element at the left pointer is negative, move left pointer one step to the right. b. If the element at the right pointer is positive, move right pointer one step to the left. c. If the element at the left pointer is positive and the element at the right pointer is negative, swap the elements at left and right, and then move both pointers one step to the right and one step to the left, respectively.

After the above steps, all the negative numbers will be on the left side of the array, and all the positive numbers will be on the right side of the array.

Here's the C++ code to implement the algorithm:

cppCopy code

#include <iostream> #include <vector> void moveNegativesToLeft(std::vector<int>& nums) {    int left = 0;    int right = nums.size() - 1;    while (left <= right) {        if (nums[left] < 0) {            left++;        } else if (nums[right] >= 0) {            right--;        } else {            std::swap(nums[left], nums[right]);            left++;            right--;        }    } } int main() {    std::vector<int> nums = {-1, 2, -3, 4, -5, 6, -7, 8};    std::cout << "Original Array: ";    for (int num : nums) {        std::cout << num << " ";    }    std::cout << std::endl;    moveNegativesToLeft(nums);    std::cout << "Array after moving negatives to the left: ";    for (int num : nums) {        std::cout << num << " ";    }    std::cout << std::endl;    return 0; }

Example Output:

sqlCopy code

Original Array: -1 2 -3 4 -5 6 -7 8 Array after moving negatives to the left: -1 -7 -3 -5 4 6 2 8

In this code, the moveNegativesToLeft function rearranges the array so that all negative numbers appear on the left side. The time complexity of this algorithm is O(n), where n is the size of the array.