LeetCode Interview Questions and Answers
13 hand-picked LeetCode interview questions with
detailed answers. Open the interactive version above to search, filter
by difficulty, run code, bookmark questions and track your progress.
Two Sum
Optimal approach: use a hash map to store each number and its index while iterating. For each element, check whether target - nums[i] has already been seen — if it has, you have the pair.
- Time Complexity: O(n)
- Space Complexity: O(n)
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
Valid Parentheses
Given a string containing only (), [], and {}, determine if the input string is valid.
Optimal Approach: Use a Stack. Push opening brackets onto the stack. Whenever a closing bracket appears, check if it matches the top of the stack.
- Time Complexity: O(n)
- Space Complexity: O(n)
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
char top = stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.isEmpty();
}
Best Time to Buy and Sell Stock
Given an array prices where prices[i] is the stock price on day i, find the maximum profit by choosing one day to buy and one later day to sell.
Optimal Approach: Traverse the array once while maintaining the minimum price seen so far. At each step, calculate the profit if you sold today and update the maximum profit.
- Time Complexity: O(n)
- Space Complexity: O(1)
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else {
maxProfit = Math.max(maxProfit, price - minPrice);
}
}
return maxProfit;
}
Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
Optimal Approach: Use the Sliding Window technique along with a HashMap to store the last index of every character. Whenever a duplicate character is found inside the current window, move the left pointer just after its previous occurrence.
- Time Complexity: O(n)
- Space Complexity: O(min(n, charset))
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
if (map.containsKey(ch)) {
left = Math.max(left, map.get(ch) + 1);
}
map.put(ch, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Optimal Approach: Use a HashSet. As you iterate through the array, check if the current element already exists in the set. If it does, a duplicate has been found.
- Time Complexity: O(n)
- Space Complexity: O(n)
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) {
return true;
}
}
return false;
}
Valid Anagram
Given two strings s and t, return true if t is an anagram of s, otherwise return false.
Optimal Approach: Since the strings contain only lowercase English letters, use an integer frequency array of size 26. Increment the count for each character in s and decrement for each character in t. If all counts become zero, the strings are anagrams.
- Time Complexity: O(n)
- Space Complexity: O(1)
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) {
return false;
}
}
return true;
}
Merge Sorted Array
You are given two sorted integer arrays nums1 and nums2. Merge nums2 into nums1 as one sorted array.
Optimal Approach: Use three pointers starting from the end of both arrays. Compare the largest remaining elements and place the larger one at the end of nums1.
- Time Complexity: O(m+n)
- Space Complexity: O(1)
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
Squares of a Sorted Array
Given a sorted integer array nums, return an array of the squares of each number sorted in non-decreasing order.
Optimal Approach: Use two pointers at the beginning and end of the array. Compare the absolute values and place the larger square at the end of the result array.
- Time Complexity: O(n)
- Space Complexity: O(n)
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] result = new int[n];
int left = 0;
int right = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[i] = nums[left] * nums[left];
left++;
} else {
result[i] = nums[right] * nums[right];
right--;
}
}
return result;
}
Longest Repeating Character Replacement
Given a string s and an integer k, you can replace at most k characters. Return the length of the longest substring containing the same letter after performing at most k replacements.
Optimal Approach: Use a Sliding Window. Maintain the frequency of characters inside the window and keep track of the highest frequency character. If the number of characters that need replacement exceeds k, shrink the window from the left.
- Time Complexity: O(n)
- Space Complexity: O(1) (26 uppercase letters)
public int characterReplacement(String s, int k) {
int[] freq = new int[26];
int left = 0;
int maxFreq = 0;
int maxLength = 0;
for (int right = 0; right < s.length(); right++) {
maxFreq = Math.max(maxFreq, ++freq[s.charAt(right) - 'A']);
while ((right - left + 1) - maxFreq > k) {
freq[s.charAt(left) - 'A']--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
Maximum Average Subarray I
Given an integer array nums consisting of n elements and an integer k, find the contiguous subarray of length k that has the maximum average value and return that value.
Optimal Approach: Compute the sum of the first window of size k. Then slide the window by removing the leftmost element and adding the next element. Track the maximum window sum.
- Time Complexity: O(n)
- Space Complexity: O(1)
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < nums.length; i++) {
sum = sum - nums[i - k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
}
Next Greater Element I
You are given two arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, find the first greater element to its right in nums2. If none exists, return -1.
Optimal Approach: Traverse nums2 using a Monotonic Decreasing Stack. Whenever the current number is greater than the stack's top, it becomes the next greater element for all smaller numbers popped from the stack. Store these mappings in a HashMap.
- Time Complexity: O(n + m)
- Space Complexity: O(n)
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> stack = new Stack<>();
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums2) {
while (!stack.isEmpty() && num > stack.peek()) {
map.put(stack.pop(), num);
}
stack.push(num);
}
while (!stack.isEmpty()) {
map.put(stack.pop(), -1);
}
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = map.get(nums1[i]);
}
return result;
}
Next Greater Element II
Given a circular integer array nums, return the next greater number for every element. If no greater element exists, return -1.
Optimal Approach: Since the array is circular, iterate through it twice using modulo (i % n). Maintain a Monotonic Decreasing Stack of indices. Whenever a greater value is found, update the answer for indices popped from the stack.
- Time Complexity: O(n)
- Space Complexity: O(n)
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 2 * n; i++) {
int index = i % n;
while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
result[stack.pop()] = nums[index];
}
if (i < n) {
stack.push(index);
}
}
return result;
}
Daily Temperatures
Given an array temperatures, return an array where each element represents the number of days you have to wait until a warmer temperature. If there is no future warmer day, return 0.
Optimal Approach: Use a Monotonic Decreasing Stack that stores indices. Whenever a warmer temperature is found, pop indices from the stack and calculate the distance between the current day and the popped day.
- Time Complexity: O(n)
- Space Complexity: O(n)
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int index = stack.pop();
answer[index] = i - index;
}
stack.push(i);
}
return answer;
}
