Binary Array Segregation

In this blog, we’ll explore a JavaScript function that manipulates an array using the two-pointer technique. The function, named twoSum, is designed to reorder elements in an array based on specific conditions. Let’s dive into its implementation, functionality, and the underlying logic.

The Problem Statement

Given an array nums consisting of binary values (0s and 1s), rearrange the array so that all zeros appear on the left and all ones appear on the right. The function should do this in-place without using extra space, and it should return the modified array.

Input:

• nums: An array of integers consisting only of 0s and 1s.

Output:

• A reordered array where all 0s are moved to the left and all 1s to the right.

Example:

Input

nums = [0, 1, 1, 0, 1, 0, 0]

Output
[0, 0, 0, 0, 1, 1, 1]

  var twoSum = function(nums){
      let len = nums.length
      start = 0;
      end = nums.length -1;
      while(start<end){
          if(nums[start]>nums[end]){
             nums[start] = nums[start]+nums[end]
             nums[end]= nums[start] - nums[end]
             nums[start] = nums[start] - nums[end]
             start = start + 1
             end = end - 1
          }else if(nums[start]+nums[end]>0){
              end = end -1;
          }else{
          start = start + 1
          }
      }
      return nums
  }

   console.log(twoSum ([0,1,1,0,1,0,0]));

  /*output [
    0, 0, 0, 0,
    1, 1, 1
  ] *?

Why This Works

The two-pointer technique ensures that the array is processed efficiently with a time complexity of O(n). By using the conditions:

• The array is rearranged such that zeros are moved to the left.

• Ones are shifted to the right without additional memory allocation or external libraries.

A Closer Look at Swapping

The swapping logic avoids using a temporary variable by leveraging simple arithmetic:

• a = a + b

• b = a - b

• a = a - b

This is a clever trick but should be used cautiously. If the numbers are large, there’s a risk of exceeding the number limits in JavaScript.

When to Use This Pattern

The two-pointer approach is useful for:

• Rearranging or partitioning arrays.

• Finding pairs that meet specific criteria (e.g., sum, difference).

• Problems involving sorted arrays.

---

Second Approach

This approach counts the number of 1s and builds a new array accordingly.

Here’s the implementation of the twoSumNew function:

var twoSumNew = function(nums){
    const len = nums.length;
    let sum = 0;
    let newArray = [];
    for(let i=0; i<len;i++){
        if(nums[i]==1){
            sum += 1;
        }
    }
    for(let i=0; i<len; i++){
        if(i<len-sum){
            newArray.push(0)
        }else{
            newArray.push(1)
        }
    }
    return newArray
}

Explanation of the Code

1. Counting 1s: A for loop traverses the array and increments a sum variable for each 1 encountered. This gives the total number of 1s in the array.

2. Building the New Array: Another for loop iterates through the array:

   • If the current index is less than len - sum, it appends 0 to the new array.

   • Otherwise, it appends 1.

3. Return Statement: After constructing the new array, it is returned as the output.

Comparison of the Two Approaches

Conclusion

The twoSum function demonstrates how efficient array manipulation can be achieved using the two-pointer technique. Understanding the logic behind the swapping and condition checks helps in crafting similar solutions for other problems. Next time you encounter an array challenge, consider whether the two-pointer approach can simplify your solution!