Added 3 medium solutions to sorting

varunu28 · varunu28 · commit 7f4f94d7c9fd · 2018-09-28T09:09:01.000-07:00
diff --git a/Medium/3Sum.java b/Medium/3Sum.java
@@ -0,0 +1,45 @@
+class Solution {
+    public List<List<Integer>> threeSum(int[] nums) {
+        Set<List<Integer>> set = new HashSet<>();
+        Arrays.sort(nums);
+        for (int i=0; i<nums.length; i++) {
+            for (int j=i+1; j<nums.length; j++) {
+                int target = -1 * (nums[i] + nums[j]);
+                
+                int idx = findBinary(nums, j+1, nums.length-1, target);
+                
+                if (idx != -1) {
+                    List<Integer> temp = new ArrayList<>();
+                    temp.add(nums[i]);
+                    temp.add(nums[j]);
+                    temp.add(nums[idx]);
+                    
+                    set.add(temp);
+                }
+            }
+        }
+        
+        List<List<Integer>> ans = new ArrayList<>(); 
+        ans.addAll(set);
+        
+        return ans;
+    }
+    
+    private int findBinary(int[] nums, int start, int end, int target) {
+        while (start <= end) {
+            int mid = (start + end)/2;
+            
+            if(nums[mid] == target) {
+                return mid;
+            }
+            else if (nums[mid] > target) {
+                end = mid-1;
+            }
+            else {
+                start = mid + 1;
+            }
+        }
+        
+        return -1;
+    }
+}
diff --git a/Medium/Find First and Last Position of Element in Sorted Array.java b/Medium/Find First and Last Position of Element in Sorted Array.java
@@ -0,0 +1,58 @@
+class Solution {
+    public int[] searchRange(int[] nums, int target) {
+        int idx = findBinary(nums, 0, nums.length-1, target);
+        int startIdx = idx;
+        int endIdx = idx;
+        
+        int start = 0;
+        int end = idx - 1;
+        
+        while (true) {
+            int temp = findBinary(nums, start, end, target);
+            if (temp != -1) {
+                startIdx = temp;
+                start = 0;
+                end = temp - 1;
+            }
+            else {
+                break;
+            }
+        }
+        
+        start = idx + 1;
+        end = nums.length - 1;
+        
+        while (true) {
+            int temp = findBinary(nums, start, end, target);
+            if (temp != -1) {
+                endIdx = temp;
+                start = temp + 1;
+                end = nums.length - 1;
+            }
+            else {
+                break;
+            }
+        }
+        
+        int[] ans = new int[]{startIdx, endIdx};
+            
+        return ans;
+    }
+    
+    private int findBinary(int[] nums, int start, int end, int target) {
+        while (start <= end) {
+            int mid = (start + end)/2;
+            if (nums[mid] == target) {
+                return mid;
+            }
+            else if (nums[mid] > target) {
+                end = mid-1;
+            }
+            else {
+                start = mid + 1;
+            }
+        }
+        
+        return -1;
+    }
+}
diff --git a/Medium/Merge Intervals.java b/Medium/Merge Intervals.java
@@ -0,0 +1,55 @@
+/**
+ * Definition for an interval.
+ * public class Interval {
+ *     int start;
+ *     int end;
+ *     Interval() { start = 0; end = 0; }
+ *     Interval(int s, int e) { start = s; end = e; }
+ * }
+ */
+class Solution {
+    public static List<Interval> merge(List<Interval> intervals) {
+
+        if (intervals.size() == 1) {
+            return intervals;
+        }
+
+        List<Interval> ans = new ArrayList<>();
+        if (intervals.size() == 0) {
+            return ans;
+        }
+
+        Collections.sort(intervals, new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                return o1.start - o2.start;
+            }
+        });
+
+        int i = 0;
+        Interval prevInterval = null;
+
+        List<Interval> temp = new ArrayList<>(intervals);
+
+        for (Interval interval : temp) {
+            if (i == 0) {
+                prevInterval = interval;
+                i++;
+                continue;
+            }
+
+            if (interval.start <= prevInterval.end) {
+                if (interval.end >= prevInterval.end) {
+                    prevInterval.end = interval.end;
+                }
+
+                intervals.remove(interval);
+            }
+            else {
+                prevInterval = interval;
+            }
+        }
+
+        return intervals;
+    }
+}
