**Problem Statement**

Given an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time.

**Solution**

[Read more…]

**Problem Statement**

Given an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time.

**Solution**

[Read more…]

**Problem Statement:**

Given an array a of n integers find all possible Pythagorean triplets from the array.

A Pythagorean triple consists of three positive integers a, b, and c, such that a^{2} + b^{2} = c^{2}. this formula is derived from Pythagoras theorem: *“For every right angle triangle with side lengths a, b, and c=> a*^{2} + b^{2} = c^{2}“.

**Solution:**

[Read more…]

**Problem Statement:**

Given a set S of n integers find all possible subsets(a,b,c) such that a + b + c = 0.

**Solution:**

Brute force approach is of O(n^4) but we can solve it in O(n^2) by using the approach in Non duplicate pairs that sum to S.

First sort the array(Order O(nlogn)), than finding a, b, c pairs is equal to finding=> For every element a in the array, if there exists a pair with sum equal to -a. As explained in Non duplicate pairs that sum to S, we can get the pair with sum -a in O(n) and we have to repeat this exercise n times so order of complexity will be O(n^2).

Given an array of n elements, write an algorithm to rotate it right by k element without using any other array. In other words rotate an array in place.

you can have temp variable to swap two elements.

Ex:-

Initial Array: A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Rotating array A right by 3 elements should result in

A = {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}

**Hint:** There is a trick, think before doing much of the programming 🙂

See Solution: Rotate an array by k elementsHide Solution

For example

Array A after reversing whole array: {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

Array A after reversing 0 to 2 elements: {8, 9, 10, 7, 6, 5, 4, 3, 2, 1}

Array A after reversing 3 to 9 elements: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}

void rotateRight(int[] a, int k){ int length = a.length();//in C/C++ it will be given as input reverse(a, 0, length -1);//reverse whole array reverse(a, 0, k-1);//assuming 0 < k < length reverse(1, k, n-1); } void reverse(int[] a, int start, int end){ while(start < end){ swap(a, start, end); start++; end--; } } void swap(int[] a, int pos1, int pos2){ int temp = a[pos1]; a[pos1]= a[pos2]; a[pos2] = temp; } //Note: in interviews you might be asked to handle negative scenarios // like array out of bound etc.