### Valid Palindrome - Leet Code Solution

Problem Statement Given a string, determine if it is a palindrome, considering…

May 19, 2019

** Inversion
There is an array(a) and two indexes i and j. Inversion is the element for whom **i < j** and **a[i] > a[j]**

Example:

```
2 6 5 4 8
# Inversion pairs
(6, 5) (6, 4) (5, 4)
# Total inversion = 3
```

Lets look at simple brute force algorithm:

```
public void calculate_bad(int[] arr) {
int count = 0;
for (int i=0; i<arr.length-1; i++) {
for (int j=i+1; j<arr.length; j++) {
if (arr[i] > arr[j]) {
count ++;
System.out.println(arr[i] + " " + arr[j]);
}
}
}
System.out.println("Total inversions: " + count);
}
```

Above is a simple algorithm. Lets think about optimizing this.

Next better number than **O(n^2)** is **O(n log n)**
Can we do it in O(n log n)? Can we apply divide and conquer algorithm in this? If somehow, we can think what we will achieve by dividing the input array?

**Hint** Can we use Merge Sort?
Yes

**How**
In function where we merge two sorted sub-problems. Before sorting, their positions are actually relatively left and right which we want.
The advantage of using merge sort is that, we know each of left and right array is sorted.

So, while comparing, one thing is for sure. For every element in left array, the index-i is always lesser than the index from right sorted sub-array. If we know, that one element in left sub-array which is greater than an element from right array.

In above image, we know in left array that index=4 element is greater than element in right array at index=2 WHat it means, we found one inversion pair. In addition to that, we know every element in left array from index=4 onwards will be greater than element in right array where we found at index=2 Which means, in above example, we found total 3 inversion pairs for this condition.

And, we keep on continuing like this.

```
private void calculate_good_recursive(int[] arr, int l, int m, int r) {
int l1 = m-l+1;
int l2 = r-m;
int[] left = new int[l1];
for (int i=0; i<l1; i++) {
left[i] = arr[l+i];
}
int[] right = new int[l2];
for (int i=0; i<l2; i++) {
right[i] = arr[m+i+1];
}
int lindex = 0;
int rindex = 0;
while (lindex < l1 && rindex < l2) {
if (right[rindex] < left[lindex]) {
for (int jj=lindex; jj<l1; jj++) {
System.out.println(left[jj] + " " + right[rindex]);
}
}
if (left[lindex] <= right[rindex]) {
arr[l] = left[lindex];
lindex ++;
}
else {
arr[l] = right[rindex];
rindex ++;
}
l++;
}
while (lindex < l1) {
arr[l] = left[lindex];
l++; lindex ++;
}
while (rindex < l2) {
arr[l] = right[rindex];
l++; rindex ++;
}
}
public void inversions_merge_sort_method(int[] arr, int l, int r) {
if (l < r) {
int m = (l+r)/2;
inversions_merge_sort_method(arr, l, m);
inversions_merge_sort_method(arr, m+1, r);
calculate_good_recursive(arr, l, m, r);
}
}
```

Problem Statement Given a string, determine if it is a palindrome, considering…

Problem Statement Given a string, find the length of the longest substring…

Sorting Problems Merge Sort Quick Sort Heap Sort Bubble Sort Selection Sort…

Problem Statement Given a string s, return the maximum number of unique…

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

Counting sort runs on relatively smaller set of input. Counting sort calculates…

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…