### Four Sum - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, are…

May 11, 2019

Its a kind of incremental insertion technique, where the algorithm build up sorting by first sorting n-1 items.

Or, we can say that we pick an element on n-1 items, and insert in a position where all items on the left side are less than or equal to this number.

The algorithm works in two loops, where outer most loop iterate over complete array. To be more precise, We iterate from index-1 to end of array. Leaving index-0 to be used by inner loop.

In inner loop, the loop variable takes the index from outer loop index variable. It takes a backup of the value present on that index, and go backward toward 0-index. It shift previous elements to next position unless they are greater than the value for which we have taken backup.

In short, inner loop tries to sort the n-1 part of array by shifting any bigger element to right. And, **insert** the element to the final position.

See the code here:

```
public void sort(int[] arr) {
int len = arr.length;
for (int i=1; i<len; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
```

- It does not use extra memory. And, is in-place algorithm.
- Its stable, as it does not change order of same value elements.
- It is more efficient in practice than Bubble Sort and Selection Sort
- It is well suited for small data sets.

The algorithm runs on O(n^2) in worst case.

Problem Statement Given an array nums of n integers and an integer target, are…

Problem Statement Given a linked list, swap every two adjacent nodes and return…

Its every software engineer’s dream to work with the big FAANG companies…

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

Problem Statement Given a signed integer, reverse digits of an integer. Return…

Problem Implement an algorithm to determine if a string has all the characters…

In this post, we will see some of the frequently used concepts/vocabulary in…

System design interview is pretty common these days, specially if you are having…

Introduction You are given an array of integers with size N, and a number K…

Graph Topological Sorting This is a well known problem in graph world…

Problem Statement Given a Binary tree, print out nodes in level order traversal…

Problem Statement Given an array nums of n integers and an integer target, are…