Skip to main content

MAY-23 2020 Challenge

Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Example 1:
Interval list intersection explaining figure
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Note:


0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.


SOLUTION IN JAVA :

class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> ans = new ArrayList();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi)
ans.add(new int[]{lo, hi});
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return ans.toArray(new int[ans.size()][]);
}
}

Comments

Popular posts from this blog

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Number of Connected Components in an Undirected Graph (Python)

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...

Leetcode 347. Top K Frequent Elements. Python (Bubble Sort)

Top K Frequent Elements Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: 1 <= nums.length <= 10 5 -10 4  <= nums[i] <= 10 4 k  is in the range  [1, the number of unique elements in the array] . It is  guaranteed  that the answer is  unique .   Follow up:  Your algorithm's time complexity must be better than  O(n log n) , where n is the array's size. Solution : class Solution:     def topKFrequent(self, n: List[int], k: int) -> List[int]:                  # [1,1,1,2,2,3] &  k = 2                  f = [[] for i in range(len(n) + 1)]         # f = [...