Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Approach: Use binary search.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

int peakIndex(int *arr, int low, int high){ if(low == high){ return low; } if(low + 1 == high){ if(arr[low] >= arr[high]){ return low; }else{ return high; } } int mid = (low + high) / 2; if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){ return mid; }else if(arr[mid] < arr[mid - 1]){ //peak lies on the left since arr[mid - 1] > arr[mid] && arr[0] = -infinity so there has to be an element which is peak on the left return peakIndex(arr, low, mid - 1); }else{ //peak lies on the right return peakIndex(arr, mid + 1, high); } } int findPeakElement(int* nums, int numsSize) { return peakIndex(nums, 0, numsSize - 1); }

Read More

69. Sqrt(x)

Implement int sqrt(int x).

Return the floor if x is not a perfect square.

Approach :  Using binary search making sure that overflow does not happen by taking long long.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public: int mySqrt(int x) { if(x <= 1){ return x; } int low = 0, high = x / 2; //long to prevent overflow long long mid; while(low <= high){ mid = (low + high) / 2; //needs to be long to prevent overflow long long t = mid * mid; //second part is to return floor if x is not perfect square if( t == x || ((t < x) && ((mid + 1) * (mid + 1) > x))){ break; } else if(x < t){ high = mid - 1; }else{ low = mid + 1; } } return mid; } };

Here is the link to the ideone solution : http://ideone.com/taTCKu

Read More

Search a 2D Matrix I

This matrix has the following properties:
        1. Integers in each row are sorted from left to right.
        2. The first integer of each row is greater than or equal to the last integer of the previous row.
    Example:
    [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]
    Given target = 3, return 1 ( 1 corresponds to true )

Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem

Approach : Use binary search to first find the row number then use binary search in that row to find the exact cell.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include<iostream> using namespace std; bool searchMatrix(int matrix[][4], int matrixRowSize, int matrixColSize, int target) { int mid; int low = 0, row; int high = matrixRowSize - 1; row = -1; while(low <= high){ mid = (low + high) / 2; if(target <= matrix[mid][matrixColSize - 1] && target >= matrix[mid][0]){ row = mid; break; }else if(target < matrix[mid][0]){ high = mid - 1; }else if(target > matrix[mid][matrixColSize - 1]){ low = mid + 1; } } low = 0; high = matrixColSize - 1; if(row != -1){ while(low <= high){ mid = (low + high) / 2; if(matrix[row][mid] == target){ return true; }else if(matrix[row][mid] < target){ low = mid + 1; }else{ high = mid - 1; } } } return false; } int main(){ int matrix[3][4] = { {1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50} }; cout << searchMatrix(matrix, 3, 4, 3); return 0; }

Read More

Majority Element in a Sorted Array

Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.

Approach: Use binary search to find the first occurrence of x in the array.
TC  = O(log(n)) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <cmath> using namespace std; int binsrch(int *arr, int x, int low, int high){ if(low <= high){ int mid = (low + high) / 2; // returns the first occurrence of x if(arr[mid] == x && (arr[mid] > arr[mid - 1] || mid == 0)){ return mid; } if(x > arr[mid]){ return binsrch(arr, x, mid + 1, high); } else{ return binsrch(arr, x, low, mid - 1); } } return -1; } int isMajority(int *arr, int x, int n){ int first = binsrch(arr, x, 0, n - 1); if(first == -1){ return 0; } if((first + n/2) <= (n - 1) && arr[first + n/2] == x){ return 1; } return 0; } using namespace std; int main(){ int arr[] ={1, 2, 3, 4, 4, 4, 4}; int n = sizeof(arr)/sizeof(arr[0]); int x = 4; if(isMajority(arr, x, n)){ cout << x << " is the majority element." << endl; } else{ cout << x << " is not the majority element." << endl; } return 0; }

Read More

Pow(X, n)

Implement a function that takes two integers and returns x^n.
Approach : Using divide and conquer to calculate the power. Remember to handle both positive and negative powers. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: double myPower(double x, int n){ if(n == 0){ return 1; } double res = myPower(x, n / 2); //if n is even, then x ^ n = x ^ n/2 * x ^ n/2 if(n % 2 == 0){ return res * res; } //else x ^ n = x ^ n/2 * x ^ n/2 * x else { return res * res * x; } } double myPow(double x, int n) { //if n < 0 return 1 / power(x, -n) if(n < 0){ return 1 / myPower(x, -1 * n); }else{ return myPower(x, n); } } };

Read More

Guess Number

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower

 1 : My number is higher

 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

Approach : Use binary search to find the given number.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// Forward declaration of guess API. // @param num, your guess // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0 int guess(int num); class Solution { public: int guessNumber(int n) { int low = 1, high = n, mid; while(low <= high){ mid = low + ((high - low) >> 1); if(guess(mid) == 0){ return mid; }else if(guess(mid) == -1){ high = mid - 1; }else{ low = mid + 1; } } return -1; } };

Read More