891315. Earliest Common Slot
Medium
Earliest Common Slot
Slug: earliest-common-slot Difficulty: Medium Id: 891315 Topic Tags: Sorting, two-pointer-algorithm, Arrays, Data Structures, Algorithms Company Tags: Amazon, Microsoft, PayPal, Google, Uber
Summary
The problem is about finding the earliest common slot between two arrays of time slots. The goal is to find the first slot where both arrays have at least one time slot. This problem involves sorting and using a two-pointer algorithm.
Detailed Explanation
To solve this problem, we will create a two-pointer approach that iterates through both arrays simultaneously. We initialize two pointers, i and j, to point to the beginning of each array.
- Initialize the earliest common slot as -1.
- Loop until either array is exhausted:
- If the current time slots at both arrays are equal (i.e.,
arr1[i] == arr2[j]), update the earliest common slot and increment both pointers (i++,j++). - If
arr1[i] < arr2[j], incrementi. - If
arr2[j] < arr1[i], incrementj.
- If the current time slots at both arrays are equal (i.e.,
- Return the earliest common slot.
Here is a step-by-step breakdown of the solution:
Time Complexity: O(n + m), where n and m are the sizes of both arrays.
Space Complexity: O(1).
Optimized Solutions
Java
public class EarliestCommonSlot {
public static int earliestCommonSlot(int[] arr1, int[] arr2) {
int i = 0, j = 0;
int earliestSlot = -1;
while (i < arr1.length && j < arr2.length) {
if (arr1[i] == arr2[j]) {
earliestSlot = arr1[i];
i++;
j++;
} else if (arr1[i] < arr2[j]) {
i++;
} else {
j++;
}
}
return earliestSlot;
}
}