Category: Sorting Problem

Sorting Problem

3 Sum

Tech CornerLeave a comment

Problem

Given an integer array arr of size n, find all magic triplets in it.

Magic triplet is a group of three numbers whose sum is zero.

Note that magic triplets may or may not be made of consecutive numbers in arr.

Example

{
"arr": [10, 3, -4, 1, -6, 9]
}

Output:

["10,-4,-6", "3,-4,1"]

Solution

function find_zero_sum(arr) {
    // Write your code here.
    var len = arr.length;
    var ans = [];
    arr.sort((a,b) => (a-b));
    
    for(var i=0; i < len-1; i++) {
        
        var s = new Set();
        
        for(var j = i+1; j < len; j++) {
            
            var x = -(arr[i] + arr[j]);
            
            if(s.has(x)) {
                var k = x + "," + arr[i] + "," + arr[j];
                ans.push(k);
            } else {
                s.add(arr[j]);
            }
        }
    }
    
    return ans;
}

Time and Space Complexity

Time Complexity : O(n3)
Space Complexity:  O(1)
Sorting · Sorting Problem

Merge One Sorted Array Into Another

Tech CornerLeave a comment

Problem

First array has n positive numbers, and they are sorted in the non-descending order.

Second array has 2n numbers: first n are also positive and sorted in the same way but the last n are all zeroes.

Merge the first array into the second and return the latter. You should get 2n positive integers sorted in the non-descending order.

Example

{
"first": [1, 3, 5],
"second": [2, 4, 6, 0, 0, 0]
}

Output:

[1, 2, 3, 4, 5, 6]

Solution

function merge_one_into_another(first, second) {
    // Write your code here.
    var n = first.length;
    var top = n-1;
    var bottom = n-1;
    var k = second.length -1;
    
    while(top >= 0 && bottom >=0){
        if(first[top] >= second[bottom]) {
            second[k] = first[top];
            top-=1;
            k-=1;
        } else {
            second[k] = second[bottom];
            bottom-=1;
            k-=1;
        }
    }
    
    while(top >=0){
        second[k] = first[top];
        top-=1;
        k-=1;
    }
    
    return second;
}

Time and Space Complexity

Time Complexity : O(1)
Space Complexity:  O(n)
Sorting Problem

Dutch National Flag

Tech CornerLeave a comment

Problem

Given some balls of three colors arranged in a line, rearrange them such that all the red balls go first, then green and then blue ones.

Do rearrange the balls in place. A solution that simply counts colors and overwrites the array is not the one we are looking for.

This is an important problem in search algorithms theory proposed by Dutch computer scientist Edsger Dijkstra. Dutch national flag has three colors (albeit different from ones used in this problem).

Example

{
"balls": ["G", "B", "G", "G", "R", "B", "R", "G"]
}

Output:

["R", "R", "G", "G", "G", "G", "B", "B"]

There are a total of 2 red, 4 green and 2 blue balls. In this order they appear in the correct output.

Solution

function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
} 
function dutch_flag_sort(balls) {
    // Write your code here.
    var first=0;
    var last = balls.length-1;
    var i=0;
    
    while(i <= last){
        if(balls[i] == 'G'){
            i++;
        } else if(balls[i] == 'R'){
            swap(balls, i, first);
            first++;
            i++;
        } else {
            swap(balls, i, last);
            last--;
        }
    }
    
    return balls;
}

Time and Space Complexity

Time Complexity : O(1)
Space Complexity:  O(n)
Sorting Problem

Segregate Even And Odd Numbers

Tech CornerLeave a comment

Problem

Given an array of numbers, rearrange them in-place so that even numbers appear before odd ones.

Example

{
"numbers": [1, 2, 3, 4]
}

Output:

[4, 2, 3, 1]

The order within the group of even numbers does not matter; same with odd numbers. So the following are also correct outputs: [4, 2, 1, 3], [2, 4, 1, 3], [2, 4, 3, 1].

Solution

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function segregate_evens_and_odds(numbers) {
    // Write your code here.
    
    //Initialize two index variables left and right
    var j = -1, i=0;
    
    while (i != numbers.length) {
        //If even number swap odd with even
        if(numbers[i]%2 == 0) {
            j++;
            swap(numbers, j, i);
        }
        i++;
    }
    
    return numbers;
}

Time and Space Complexity

Time Complexity : O(n)
Space Complexity:  O(n)