Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

void moveZeroes(int* nums, int numsSize){ int i = 0, j = 0; for(i = 0; i < numsSize; i++){ //copy non-zero elements if(nums[i] != 0){ nums[j] = nums[i]; j++; } } //put zeros in the end while(j < numsSize){ nums[j++] = 0; } }

Read More

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

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

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

bool isPalindrome(char* s) { int i, j, len; len = strlen(s); i = 0; j = len - 1; while(i < j){        // skip non alpha chars from start        while(i < len && !isalnum(s[i])){ i++; }         // skip non alpha chars from end        while(j >= 0 && !isalnum(s[j])){ j--; }         if(i < j && tolower(s[i]) != tolower(s[j])){ return false; }         i++; j--; } return true; }

Read More

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

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

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int height(TreeNode *root){ if(root == NULL){ return 0; } int leftHeight = height(root->left); if(leftHeight == -1){ return -1; } int rightHeight = height(root->right); if(rightHeight == -1){ return -1; } if(abs(leftHeight - rightHeight) > 1){ return -1; } return 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { if(root == NULL){ return true; } if(height(root) == -1){ return false; } return true; } };

Read More

Leaders in an array

An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader.
For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <iostream> using namespace std; int main(){ int arr[] = {18, 16, 17, 4, 3, 5, 2}; int n = sizeof(arr)/sizeof(arr[0]); int maxSoFar = arr[n - 1]; cout << maxSoFar << " "; for(int i = n - 2; i >= 0 ; i--){ if(arr[i] > maxSoFar){ cout << arr[i] << " "; maxSoFar = arr[i]; } } cout << endl; return 0; }

Read More