Added 3 medium solutions

varunu28 · varunu28 · commit 00d48783345a · 2018-09-27T08:59:28.000-07:00
diff --git a/Medium/Find Peak Element.java b/Medium/Find Peak Element.java
@@ -0,0 +1,39 @@
+class Solution {
+    public static int findPeakElement(int[] nums) {
+        if (nums.length == 1) {
+            return 0;
+        }
+        
+        return findPeakElementImpl(nums, 0, nums.length-1);
+    }
+
+    private static int findPeakElementImpl(int[] nums, int start, int end) {
+        if (start > end) {
+            return -1;
+        }
+
+        int mid = (start + end)/2;
+
+        if (mid == 0 && nums.length > 1) {
+            if (nums[mid] > nums[mid+1]) {
+                return mid;
+            }
+        }
+        else if (mid == nums.length-1 && nums.length > 1) {
+            if (nums[mid] > nums[mid-1]) {
+                return mid;
+            }
+        }
+        else {
+            if (nums.length > 1) {
+                if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
+                    return mid;
+                }
+            }
+        }
+
+        int left = findPeakElementImpl(nums, start, mid-1);
+
+        return left == -1 ? findPeakElementImpl(nums, mid+1, end) : left;
+    }
+}
diff --git a/Medium/Kth Largest Element in an Array.java b/Medium/Kth Largest Element in an Array.java
@@ -1,13 +1,18 @@
 class Solution {
-    public int findKthLargest(int[] nums, int k) {
-        Arrays.sort(nums);
-        int i = 0;
-        int j = nums.length;
-        while (i<k) {
-            i++;
-            j--;
+    public static int findKthLargest(int[] nums, int k) {
+        PriorityQueue<Integer> queue = new PriorityQueue<>(k);
+        for (int i=0; i<nums.length; i++) {
+            if (queue.size() < k) {
+                queue.add(nums[i]);
+            }
+            else {
+                if (nums[i] > queue.peek()) {
+                    queue.remove();
+                    queue.add(nums[i]);
+                }
+            }
         }
-        
-        return nums[j];
+
+        return queue.remove();
     }
 }
diff --git a/Medium/Letter Combinations of a Phone Number.java b/Medium/Letter Combinations of a Phone Number.java
@@ -0,0 +1,46 @@
+class Solution {
+    public static List<String> letterCombinations(String digits) {
+        Map<Integer, String> map = new HashMap<>();
+
+        map.put(2, "abc");
+        map.put(3, "def");
+        map.put(4, "ghi");
+        map.put(5, "jkl");
+        map.put(6, "mno");
+        map.put(7, "pqrs");
+        map.put(8, "tuv");
+        map.put(9, "wxyz");
+
+        ArrayList<String> result = new ArrayList<String>();
+        if(digits == null || digits.length() == 0) {
+            return result;
+        }
+
+        ArrayList<Character> temp = new ArrayList<Character>();
+        updateResult(digits, temp, result, map);
+
+        return result;
+    }
+
+    private static void updateResult(String digits, ArrayList<Character> temp, ArrayList<String> result, Map<Integer, String> map) {
+        if (digits.length() == 0) {
+            char[] charArray = new char[temp.size()];
+
+            for (int i=0; i<temp.size(); i++) {
+                charArray[i] = temp.get(i);
+            }
+
+            result.add(String.valueOf(charArray));
+            return;
+        }
+
+        Integer curr = Integer.valueOf(digits.substring(0, 1));
+        String letters = map.get(curr);
+
+        for (int i=0; i<letters.length(); i++) {
+            temp.add(letters.charAt(i));
+            updateResult(digits.substring(1), temp, result, map);
+            temp.remove(temp.size()-1);
+        }
+    }
+}
diff --git a/Medium/Unique Paths.java b/Medium/Unique Paths.java
@@ -0,0 +1,22 @@
+class Solution {
+
+    public int uniquePaths(int m, int n) {
+        int[][] arr = new int[m][n];
+        return getCount(arr, m, n);        
+    }
+    
+    private int getCount(int[][] arr, int m, int n) {
+        for (int i=0; i<arr.length; i++) {
+            for (int j=0; j<arr[0].length; j++) {
+                if (i == 0 || j ==0) {
+                    arr[i][j] = 1;
+                }
+                else {
+                    arr[i][j] = arr[i-1][j] + arr[i][j-1];
+                }
+            }
+        }
+        
+        return arr[m-1][n-1];
+    }
+}
