Given an integer array, find all pairs that sum up to a specific value k

This is one of the basic interview question about algorithm about finding the two numbers from array such that there sum is equal to K.
In this post, we'll look into different approaches for finding all the pair of integer such that there sum is equal to K.

Approach 1 Brute-Force
In this approach, for each input element check whether there is any element exist whose sum is K. This can be solved with just two loops.

Time Complexity : O(n^2) for nested loops, Space Complexity : O(1)

Approach 2 
In this approach, we first sort the array using merge or heap sort which give O(nlogn) complexity. Then on sorted array we main two indices, i point to starting index and j point to last element index. We compute A[i]+A[j]. If sum equals K, then we found the pair increment both i & j. If the sum is less then k, increment i, if sum is greater than K decrements j.

Time Complexity : O(nlogn) if array is already sorted then complexity would be O(n), Space Complexity : O(1)

Approach 3 
In this approach we use HashMap, our task is find two indexes of the array whose sum is K i.e, A[i]+A[j]=K. For each input element A[i] we check whether K-A[i] also exist in the Hash map. key will be array element, value will be index of element.

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



If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

Find Next Higher Number With Same Digits

Write a program to find the next highest number by rearranging the digits of a number. For instance, 
If input is 13483 then output must be 13834.

Test cases:
Input     Output
3971     7139
83971   87139
54321   54321
405321 410235


Logic:
Let take a numner 12543 and resulting next higher number is 13245. 
Scan the digits from the tenths digit going towards left (which is 4 in our case) 
At each iteration we check the right digit of the current digit we are at and if the value of the right is greater then current we stop other continue to left 
4>3 continue 
5>4 contine 
2>5 stop 
2 is our pivot element. 
from the digit 2 to the right we find the smallest higher digit of resulting number 2 which 3. 
swap the 3 with 2, it will become 13542. now 3 is our pivot element. 
Now revere the number to right pivot element i.e 3 , it comes 13245 result. 
Note : in case of repeating digit like 147553 we need to swap the 4 with the rightmost digit, otherwise we don't get the highest number. 
Time complexity would be O(n)

Code : 

If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...