### Container with Most Water - Leet Code Solution

Problem Statement Given n non-negative integers a1, a2, …, an , where each…

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 n non-negative integers a1, a2, …, an , where each…

A number consists of digits. Example: 843. Its a 3-digit number. Radix sort…

This topic is one of the most common studied. When somebody started preparation…

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

Problem Statement Say you have an array prices for which the ith element is the…

Problem Statement Given an array of integers, find if the array contains any…

Introduction I was trying to upload images to my backend using rest APIs. I was…

Introduction In this post, we will see multiple ways to use annotation…

Introduction I was using Paypal payment on one of my website, and suddenly lot…

Introduction In a Spring boot app, we tend to use annotation, so that Spring…

Introduction In this posr, we will see how to prepare mysql query to fetch user…

Introduction Here, we will see the drupal code to fetch all the active users…