## Introduction

In this blog, we will try to grab hold of a single-dimensional Array data structure problem in which dynamic programming has been used. Through that problem, we will try to understand how to approach any dynamic programming array data structure problem. The examples presented will help you clear your concepts, Pseudocode will provide you with an immediate solution, and the implementation part will give you a detailed understanding of every step.

### What is an Array Data Structure?

A collection of elements stored at contiguous memory locations is an Array. The elements stored in the array are of the same type. The contiguous memory locations of the array make it easier to calculate the position of each element in the array.

The first element is at index 0. As we transverse the array, the index increases by 1 till n-1 if there are n elements in the array.

Example Array

Also Read, __Byte Array to String__

### Problem Statement

Firstly, we will have a look at what exactly the problem says.

Given an array of ‘n’ elements. We have to find the ‘kth’ smallest absolute difference of the two elements present in that array.

The absolute value of the difference between the two numbers of any pair (x, y) is defined as the absolute difference between x and y.

Here, we are assuming that all the elements in an array are positive.

**Example 1:**

Explanation: First, we will look into all the possible pairs that can be created from the nums[] and the absolute difference between them in the following table.

Given k for this example is 6. Now, we will determine the 6th smallest absolute difference, which is 8. So, 8 will be displayed as the output.

**Example 2: **For a better understanding, we will consider one more example.

First, we will look into all the possible pairs that can be created from the nums[] and the absolute difference between them in the following table.

This time we will repeat some values to see if it brings any change in the answer.

From the above table, it is clear that repeating value doesn’t bring much change. It just reduces the number of possible pairs that could have been created if there were different values.

Given k for this example is 3. Now, we will determine the 3rd smallest absolute difference, which is 4. So, 4 will be displayed as the output.

## Approach

### Why we don’t go for the Naive Approach?

What happens in the Naive Approach is that we will find absolute differences for all possible pairs as we saw in the example. Put them all in an array and sort the array. Then, according to the given ‘k’, we will traverse through that array and find the kth smallest absolute difference.

If we follow the Naive Approach, in that case, the time complexity will be equal to O(N^2(log(N)), which is not optimal at all. In such a situation, it is better if we go with the approach given below.

### What will be the optimal approach then?

We will use Binary Search Approach. The smallest absolute difference which could ever be present will be obviously zero, in case any of the values in the array is repeated. Now, we will find the maximum absolute difference, which will be the difference between the smallest and the largest elements of the array. Clearly, we know the maximum possible difference in all possible pairs will be this. We know that our output will be between these two values, so we will go for Binary Search in this problem to solve it.

**Step-1:**

We will take an example array of ‘n’ elements and k=3 as input. We will sort the array.

**Step-2:**

Now that we have sorted the array, we will find the absolute difference of all the possible pairs. Considering the example above, the lower bound is 1 and the upper bound is 8. So, the mid-value will be 4 because the decimal is ignored. We will use the Sliding Window technique with two pointers to determine the number of pairs whose differences are less than or equal to the mid-value we calculated.

**Step-4:**

Based on the results of that condition, we are going to fix our search base from lower bound to mid-value or from mid-value to upper bound and continue searching.

We will have 6 such pairs and 6 is greater than 3(k). This means our 3rd smallest absolute difference obviously lies between lower bound and mid-value.

**Step-5:**

Now, the lower bound remains 0 but the upper bound changes to 4. So, the mid-value also changes to 2. Again, we will check for the number of pairs whose absolute difference is less than or equal to 2. We will have 3 such pairs. This means our 3rd smallest absolute difference obviously lies between lower bound and mid-value.

**Step-6:**

Again, the lower bound remains 0 but the upper bound changes to 2. We will come to a situation when left meets right, that is we will be left with only one value. That’s where our search will end. And, we will get 2 as the output.

Must Read __Lower Bound in C++__

### PseudoCode

```
static boolean issmalldiff(int[] nums, int k, int mid)
{
int count = 0, left = 0;
for(int right = 1; right< nums.length; right++)
{
while(nums[right] - nums[left]> mid)
{
left++;
}
count += right-left;
}
return(count >= k);
}
```

### Implementation in Java

```
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
//function to possible absolute differences
static boolean issmalldiff(int[] nums, int k, int mid)
{
int count = 0, left = 0;
for(int right = 1; right< nums.length; right++)
{
while(nums[right] - nums[left]> mid)
{
left++;
}
count += right-left;
}
return(count >= k);
}
//function to get k-th smallest difference
public static void main(String[] args)
{
int nums[] = {10,13,7,5,11};
int k= 4;
Arrays.sort(nums);
int left = 0;
int right = nums[nums.length-1] - nums[0];
while(left<right)
{
int mid= (left+right)/2;
if(issmalldiff(nums,k,mid))
right = mid;
else
left = mid+1;
}
System.out.println(left);
}
}
```

**Input **

`nums = {10, 13, 7, 5, 11}, k= 4`

**Output **

`3`

#### Complexity Analysis

**Time Complexity **

Here, we can that there is a nested loop, that is one loop inside another the outer loop is going from 1 to n and in the worst case the inner loop will also traverse from 1 to n therefore the time complexity would be O(n*n) i.e., O(n^2)

**Space Complexity**

Since we have not used any extra space. Thus, the space complexity for the above-given code will be O(1).