To-cody

Given an array  nums  containing  n  distinct numbers in the range  [0, n] , return  the only number in the range that is missing from the array. Follow up:  Could you implement a solution using only  O(1)  extra space complexity and  O(n)  runtime complexity?   Example 1: Input: nums = [3,0,1] Output: 2 Explanation : n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums. Example 2: Input: nums = [0,1] Output: 2 Explanation : n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums. Solutions(Java): 1. class Solution { public int missingNumber ( int [] nums) { int i = 0 ; while (i < nums.length) { int correct = nums[i]; if (nums[i] < nums.length &&nums[i] != nums[correct]) swap(nums, i, correct); else

 Suppose an array of length   n   sorted in ascending order is   rotated   between   1   and   n   times. For example, the array   nums = [0,1,2,4,5,6,7]   might become: [4,5,6,7,0,1,2]  if it was rotated  4  times. [0,1,2,4,5,6,7]  if it was rotated  7  times. Notice that  rotating  an array  [a[0], a[1], a[2], ..., a[n-1]]  1 time results in the array  [a[n-1], a[0], a[1], a[2], ..., a[n-2]] . Given the sorted rotated array  nums  of  unique  elements, return  the minimum element of this array . You must write an algorithm that runs in  O(log n) time.   Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Solution(Java): import java.util.Arrays; class Solution { public int findMin(int[] nums) { Arrays.sort(nums); return nums[0]; } }

  You are given an   m x n   matrix   M   initialized with all   0 's and an array of operations   ops , where   ops[i] = [a i , b i ]   means   M[x][y]   should be incremented by one for all   0 <= x < a i   and   0 <= y < b i . Count and return  the number of maximum integers in the matrix after performing all the operations .   Example 1: Input: m = 3, n = 3, ops = [[2,2],[3,3]] Output: 4 Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4. Example 2: Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]] Output: 4 Solution(Java): class Solution { public int maxCount(int m, int n, int[][] ops) { int min=0, min1=0; if(ops.length==0){ return m*n; } else{ min=ops[0][0]; for(int i=0;i<ops.length-1;i++){ if(ops[i+1][0]<min){ min=ops[i+1][0]; }

  Given a non-negative integer   c , decide whether there're two integers   a   and   b   such that   a 2  + b 2  = c .   Example 1: Input: c = 5 Output: true Explanation: 1 * 1 + 2 * 2 = 5 Example 2: Input: c = 3 Output: false Solution(Java): class Solution { public boolean judgeSquareSum(int c) { int left=0, right=(int)Math.sqrt(c); while(left<=right){ if(left*left+right*right==c) return true; else if(left*left+right*right<c) left++; else right--; } return false; } }

  Given an integer array   nums , return   the  greatest common divisor  of the smallest number and largest number in  nums . The  greatest common divisor  of two numbers is the largest positive integer that evenly divides both numbers.   Example 1: Input: nums = [2,5,6,9,10] Output: 2 Explanation: The smallest number in nums is 2. The largest number in nums is 10. The greatest common divisor of 2 and 10 is 2. Solution(Java): class Solution { public int findGCD(int[] nums) { Arrays.sort(nums); int n= nums.length-1, temp=1; for(int i=2;i<=nums[n];i++){ if(nums[0]%i==0 && nums[n]%i==0){ if(i>temp) temp= i; } } return temp; } }

Given an array of integers   nums   sorted in ascending order, find the starting and ending position of a given   target   value. If  target  is not found in the array, return  [-1, -1] . You must write an algorithm with  O(log n)  runtime complexity. Examples: Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Input: nums = [], target = 0 Output: [-1,-1] Solution (Java): class Solution { public int[] searchRange(int[] nums, int target) { int[] ans={-1,-1}; int start=searchPosition(nums,target,true); int end=searchPosition(nums,target,false); ans[0]=start; ans[1]=end; return ans; } int searchPosition(int[]nums, int target, boolean WantStartElement){ int start=0, end=nums.length-1,ans=-1; while(start<=end){ int mid=start+(end-start)/2; if(target<nums[mid]) end=mid-1; else if(target>nums[mid]) start=mid+1; else{

   Given a characters array   letters   that is sorted in   non-decreasing   order and a character   target , return   the smallest character in the array that is larger than  target . Note  that the letters wrap around. For example, if  target == 'z'  and  letters == ['a', 'b'] , the answer is  'a' .   Example 1: Input: letters = ["c","f","j"], target = "a" Output: "c" Input: letters = ["c","f","j"], target = "j" Output: "c" Solution(Java) class Solution { public char nextGreatestLetter(char[] letters, char target) { int start=0, end= letters.length-1; while(start<=end){ int mid=start+(end-start)/2; if(letters[mid]>target) end=mid-1; else start=mid+1; } return letters[start%letters.length]; } }

  Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with  O(log n)  runtime complexity.   Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2: Input: nums = [1,3,5,6], target = 2 Output: 1 Solution(Java): class Solution { public int searchInsert(int[] nums, int target) { int start=0, end=nums.length-1; while(start<=end){ int mid= start+(end-start)/2; if(target<nums[mid]) end=mid-1; else if(target>nums[mid]) start=mid+1; else return mid; } return end+1; } }

  Given an array of integers   nums   which is sorted in ascending order, and an integer   target , write a function to search   target   in   nums . If   target   exists, then return its index. Otherwise, return   -1 . You must write an algorithm with  O(log n)  runtime complexity.   Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Solution(Java) class Solution { public int search(int[] nums, int target) { int start=0, end=nums.length-1; while(start<=end){ int mid= start+(end-start)/2; if(target<nums[mid]) end=mid-1; else if(target>nums[mid]) start=mid+1; else return mid; } return -1; } }