Top Facebook Questions
Looking to join Facebook? This problems list will give you a preliminary grasp of Facebook’s interview style and test sites, and conduct simulation exercises in advance. The list is updated based on how frequently problems appear in an interview.
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (50.82%) | 52199 | 1712 |
Companies
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2)
time complexity?
Approach:
Algorithm
The brute force approach is simple. Loop through each element and find if there is another value that equals to target−x.
Complexity Analysis
Time complexity: O(n2)O(n^2)O(n2).
For each element, we try to find its complement by looping through the rest of the array which takes O(n)O(n)O(n) time. Therefore, the time complexity is O(n2)O(n^2)O(n2).Space complexity: O(1)O(1)O(1).
The space required does not depend on the size of the input array, so only constant space is used
class Solution {
public:
vector twoSum(vector& nums, int target) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {}; // No solution found
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Hard (27.86%) | 11465 | 1918 |
Companies
Given an input string s
and a pattern p
, implement regular expression matching with support for '.'
and '*'
where:
'.'
Matches any single character.'*'
Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Constraints:
1 <= s.length <= 20
1 <= p.length <= 20
s
contains only lowercase English letters.p
contains only lowercase English letters,'.'
, and'*'
.- It is guaranteed for each appearance of the character
'*'
, there will be a previous valid character to match.
Approach:
We can use dynamic programming to solve this problem. Let dp[i][j] be a boolean value representing whether the first i characters of s match the first j characters of p.
First, we initialize dp[0][0] to true since an empty pattern matches an empty string.
Next, we need to consider the first row of the dp matrix. If the pattern p starts with a ‘‘ then it can match zero occurrences, so we set dp[0][j] to dp[0][j-2] for all j where p[j-1] == ‘‘.
Now we fill in the remaining cells of the dp matrix using the following rules:
- If the i-1th character of s matches the j-1th character of p or the j-1th character of p is ‘.’, then dp[i][j] is equal to dp[i-1][j-1].
- If the j-1th character of p is ‘*’, then we have two cases:
a) Zero occurrences: dp[i][j] is equal to dp[i][j-2]
b) One or more occurrences: dp[i][j] is equal to dp[i-1][j] if the i-1th character of s matches the j-2th character of p or the j-2th character of p is ‘.’.
Finally, we return dp[m][n], which represents whether the entire string s matches the entire pattern p.
Complexity:
Time Complexity:
The time complexity of the algorithm is O(m * n), where m and n are the lengths of s and p, respectively. This is because we need to fill in the entire dp matrix.Space Complexity:
The space complexity of the algorithm is also O(m * n) because we need to create a dp matrix of size (m+1) x (n+1).
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
std::vector> dp(m+1, std::vector(n+1, false));
dp[0][0] = true; // empty pattern matches empty string
// initialize first row (empty string)
for (int j = 1; j <= n; j++) {
if (p[j-1] == '*')
dp[0][j] = dp[0][j-2];
}
// fill in remaining cells
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i-1] == p[j-1] || p[j-1] == '.') {
dp[i][j] = dp[i-1][j-1];
} else if (p[j-1] == '*') {
dp[i][j] = dp[i][j-2]; // zero occurrences
if (s[i-1] == p[j-2] || p[j-2] == '.') {
dp[i][j] = dp[i][j] || dp[i-1][j]; // one or more occurrences
}
}
}
}
return dp[m][n];
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (59.53%) | 12528 | 738 |
Companies
Roman numerals are represented by seven different symbols: I
, V
, X
, L
, C
, D
and M
.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2
is written as II
in Roman numeral, just two ones added together. 12
is written as XII
, which is simply X + II
. The number 27
is written as XXVII
, which is XX + V + II
.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII
. Instead, the number four is written as IV
. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX
. There are six instances where subtraction is used:
I
can be placed beforeV
(5) andX
(10) to make 4 and 9.X
can be placed beforeL
(50) andC
(100) to make 40 and 90.C
can be placed beforeD
(500) andM
(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15
s
contains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M')
.- It is guaranteed that
s
is a valid roman numeral in the range[1, 3999]
.
Approach:
Certainly! Let’s break down the code and provide a clear intuition and explanation, using the examples “IX” and “XI” to demonstrate its functionality.
Intuition:
The key intuition lies in the fact that in Roman numerals, when a smaller value appears before a larger value, it represents subtraction, while when a smaller value appears after or equal to a larger value, it represents addition.
Explanation:
The unordered map
m
is created and initialized with mappings between Roman numeral characters and their corresponding integer values. For example, ‘I’ is mapped to 1, ‘V’ to 5, ‘X’ to 10, and so on.The variable
ans
is initialized to 0. This variable will accumulate the final integer value of the Roman numeral string.The for loop iterates over each character in the input string
s
.
For the example “IX”:When
i
is 0, the current characters[i]
is ‘I’. Since there is a next character (‘X’), and the value of ‘I’ (1) is less than the value of ‘X’ (10), the conditionm[s[i]] < m[s[i+1]]
is true. In this case, we subtract the value of the current character fromans
.ans -= m[s[i]];
ans -= m['I'];
ans -= 1;
ans
becomes -1.When
i
is 1, the current characters[i]
is ‘X’. This is the last character in the string, so there is no next character to compare. Since there is no next character, we don’t need to evaluate the condition. In this case, we add the value of the current character toans
.ans += m[s[i]];
ans += m['X'];
ans += 10;
ans
becomes 9.
For the example “XI”:
When
i
is 0, the current characters[i]
is ‘X’. Since there is a next character (‘I’), and the value of ‘X’ (10) is greater than the value of ‘I’ (1), the conditionm[s[i]] < m[s[i+1]]
is false. In this case, we add the value of the current character toans
.ans += m[s[i]];
ans += m['X'];
ans += 10;
ans
becomes 10.When
i
is 1, the current characters[i]
is ‘I’. This is the last character in the string, so there is no next character to compare. Since there is no next character, we don’t need to evaluate the condition. In this case, we add the value of the current character toans
.ans += m[s[i]];
ans += m['I'];
ans += 1;
ans
becomes 11.
After the for loop, the accumulated value in
ans
represents the integer conversion of the Roman numeral string, and it is returned as the result.
class Solution {
public:
int romanToInt(string s) {
unordered_map m;
m['I'] = 1;
m['V'] = 5;
m['X'] = 10;
m['L'] = 50;
m['C'] = 100;
m['D'] = 500;
m['M'] = 1000;
int ans = 0;
for(int i = 0; i < s.length(); i++){
if(m[s[i]] < m[s[i+1]]){
ans -= m[s[i]];
}
else{
ans += m[s[i]];
}
}
return ans;
}
}
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Medium (33.37%) | 28716 | 2578 |
Companies
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]]
such that i != j
, i != k
, and j != k
, and nums[i] + nums[j] + nums[k] == 0
.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
Approach:
Intuition of this Problem:
Set is used to prevent duplicate triplets and parallely we will use two pointer approach to maintain J and k.
NOTE – PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.
Approach for this Problem:
- Sort the input array
- Initialize a set to store the unique triplets and an output vector to store the final result
- Iterate through the array with a variable i, starting from index 0.
- Initialize two pointers, j and k, with j starting at i+1 and k starting at the end of the array.
- In the while loop, check if the sum of nums[i], nums[j], and nums[k] is equal to 0. If it is, insert the triplet into the set and increment j and decrement k to move the pointers.
- If the sum is less than 0, increment j. If the sum is greater than 0, decrement k.
- After the while loop, iterate through the set and add each triplet to the output vector.
- Return the output vector
//Optimized Approach - O(n^2 logn + nlogn) - o(n^2 logn) time and O(n) space
class Solution {
public:
vector> threeSum(vector& nums) {
int target = 0;
sort(nums.begin(), nums.end());
set> s;
vector> output;
for (int i = 0; i < nums.size(); i++){
int j = i + 1;
int k = nums.size() - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
s.insert({nums[i], nums[j], nums[k]});
j++;
k--;
} else if (sum < target) {
j++;
} else {
k--;
}
}
}
for(auto triplets : s)
output.push_back(triplets);
return output;
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (53.34%) | 12893 | 17009 |
Companies
Given an integer array nums
sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums
.
Consider the number of unique elements of nums
to be k
, to get accepted, you need to do the following things:
- Change the array
nums
such that the firstk
elements ofnums
contain the unique elements in the order they were present innums
initially. The remaining elements ofnums
are not important as well as the size ofnums
. - Return
k
.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
nums
is sorted in non-decreasing order.
Approach:
Intuition:
The Intuition is to use two pointers, i
and j
, to iterate through the array. The variable j
is used to keep track of the current index where a unique element should be placed. The initial value of j
is 1 since the first element in the array is always unique and doesn’t need to be changed.
Explanation:
The code starts iterating from i = 1
because we need to compare each element with its previous element to check for duplicates.
The main logic is inside the for
loop:
- If the current element
nums[i]
is not equal to the previous elementnums[i - 1]
, it means we have encountered a new unique element. - In that case, we update
nums[j]
with the value of the unique element atnums[i]
, and then incrementj
by 1 to mark the next position for a new unique element. - By doing this, we effectively overwrite any duplicates in the array and only keep the unique elements.
Once the loop finishes, the value of j
represents the length of the resulting array with duplicates removed.
Finally, we return j
as the desired result.
class Solution {
public:
int removeDuplicates(vector& nums) {
int j = 1;
for(int i = 1; i < nums.size(); i++){
if(nums[i] != nums[i - 1]){
nums[j] = nums[i];
j++;
}
}
return j;
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Medium (58.72%) | 17309 | 903 |
Companies
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4
digits[i]
is a digit in the range['2', '9']
.
Approach:
Intuition
- The logic is so simple, all you need to do is to create map similar to the phone map.
- and apply multiple neasted loops, and just keep tacking characters in sequence.
- so in case of 23, we will do the following loop
for (char c : mp[2]) for (char d : mp[3]) ans.push_back(c+d);
- And keeping in mind that if we have any 1 we should neglect them
- ie: 213 should give the same answer as 23
Approach
- Firstly define a static phone map
- Secondly remove all ones from the digits using this built it method:
digits.erase(remove(digits.begin(), digits.end(), '1'), digits.end()); // remove 1s from string
- now all we need to do is to apply the neasted loops as you can see in intuition, so to do so I used recursive method backtracking
Backtracking (i, digits, s, ans)
return type and parameters
- Return Type: it returns nothing
- Parameter:
- i: the index of the current digit.
- digits: the given string of digits.
- s: this is the formatted string till the current call.
- ans: this is the vector in which we store all possible combinations.
Basecase
- our basecase is when i is same as the length of the given digits, because all the result strings must be same length as the given digits.
- so if it happens, we should make sure that our string has at least one character, because in test case 2, he insert empty string, so we should return empty vector not {”}.
- if this happend just insert s in the result.
- then return.
recursive logic
- just loop over all characters exist in the map of the current digit, and increment i by 1 in each call and append that character to s
for (auto chr : mp[digits[i]]) backtracking(i + 1, digits, s + chr, ans)
Complexity
- Time complexity:
- O(4^l) where l is the length of the given digits string
4 not 3 because 7 & 9 contains 4 charachters, so there may be a case where we have 9999 or 7777 so it will be 4^4.
- Space complexity:
- O(4 * 4^l) = O(4 ^ (l + 1)) which is the matrix for storing all possible combinations.
class Solution {
public:
#define DPSolver ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
map> mp = {
{'2', {'a', 'b', 'c'}},
{'3', {'d', 'e', 'f'}},
{'4', {'g', 'h', 'i'}},
{'5', {'j', 'k', 'l'}},
{'6', {'m', 'n', 'o'}},
{'7', {'p', 'q', 'r', 's'}},
{'8', {'t', 'u', 'v'}},
{'9', {'w', 'x', 'y', 'z'}}};
void backtracking(int i, string digits, string s, vector &ans)
{
// base cases
if (i == digits.length())
{
if (s.length())
ans.push_back(s);
return;
}
for (auto chr : mp[digits[i]])
backtracking(i + 1, digits, s + chr, ans);
}
vector letterCombinations(string digits)
{
DPSolver;
// remove all ones
digits.erase(remove(digits.begin(), digits.end(), '1'), digits.end());
vector ans;
backtracking(0, digits, "", ans);
return ans;
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (40.19%) | 22279 | 1501 |
Companies
Given a string s
containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s
consists of parentheses only'()[]{}'
.
Approach:
Intuition
The problem requires us to determine if the given string of brackets is valid or not. We can use a stack data structure to keep track of opening brackets encountered and check if they match with the corresponding closing brackets.
Approach
Here is the step-by-step approach of the algorithm:
Initialize an empty stack.
Traverse the input string character by character.
If the current character is an opening bracket (i.e., ‘(‘, ‘{‘, ‘[‘), push it onto the stack.
If the current character is a closing bracket (i.e., ‘)’, ‘}’, ‘]’), check if the stack is empty. If it is empty, return false, because the closing bracket does not have a corresponding opening bracket. Otherwise, pop the top element from the stack and check if it matches the current closing bracket. If it does not match, return false, because the brackets are not valid.
After traversing the entire input string, if the stack is empty, return true, because all opening brackets have been matched with their corresponding closing brackets. Otherwise, return false, because some opening brackets have not been matched with their corresponding closing brackets.
Complexity
- Time complexity:
The time complexity of the solution is O(n)O(n)O(n), where n is the length of the input string. This is because we traverse the string once and perform constant time operations for each character.
- Space complexity:
The space complexity of the solution is O(n)O(n)O(n), where n is the length of the input string. This is because the worst-case scenario is when all opening brackets are present in the string and the stack will have to store them all.
class Solution {
public:
bool isValid(string s) {
stack st; // create an empty stack to store opening brackets
for (char c : s) { // loop through each character in the string
if (c == '(' || c == '{' || c == '[') { // if the character is an opening bracket
st.push(c); // push it onto the stack
} else { // if the character is a closing bracket
if (st.empty() || // if the stack is empty or
(c == ')' && st.top() != '(') || // the closing bracket doesn't match the corresponding opening bracket at the top of the stack
(c == '}' && st.top() != '{') ||
(c == ']' && st.top() != '[')) {
return false; // the string is not valid, so return false
}
st.pop(); // otherwise, pop the opening bracket from the stack
}
}
return st.empty(); // if the stack is empty, all opening brackets have been matched with their corresponding closing brackets,
// so the string is valid, otherwise, there are unmatched opening brackets, so return false
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Hard (51.04%) | 18425 | 658 |
Companies
You are given an array of k
linked-lists lists
, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i]
is sorted in ascending order.- The sum of
lists[i].length
will not exceed104
.
Approach:
Intuition of this Problem:
This solution uses the merge sort algorithm to merge all the linked lists in the input vector into a single sorted linked list. The merge sort algorithm works by recursively dividing the input into halves, sorting each half separately, and then merging the two sorted halves into a single sorted output.
Approach for this Problem:
Define a function merge that takes two pointers to linked lists as input and merges them in a sorted manner.
- a. Create a dummy node with a value of -1 and a temporary node pointing to it.
- b. Compare the first node of the left and right linked lists, and append the smaller one to the temporary node.
- c. Continue this process until either of the lists becomes empty.
- d. Append the remaining nodes of the non-empty list to the temporary node.
- e. Return the next node of the dummy node.
Define a function mergeSort that takes three arguments – a vector of linked lists, a starting index, and an ending index. It performs merge sort on the linked lists from the starting index to the ending index.
- a. If the starting index is equal to the ending index, return the linked list at that index.
- b. Calculate the mid index and call mergeSort recursively on the left and right halves of the vector.
- c. Merge the two sorted linked lists obtained from the recursive calls using the merge function and return the result.
Define the main function mergeKLists that takes the vector of linked lists as input and returns a single sorted linked list.
- a. If the input vector is empty, return a null pointer.
- b. Call the mergeSort function on the entire input vector, from index 0 to index k-1, where k is the size of the input vector.
- c. Return the merged linked list obtained from the mergeSort function call.
End of algorithm.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode *left, ListNode *right) {
ListNode *dummy = new ListNode(-1);
ListNode *temp = dummy;
while (left != nullptr && right != nullptr) {
if (left -> val < right -> val) {
temp -> next = left;
temp = temp -> next;
left = left -> next;
}
else {
temp -> next = right;
temp = temp -> next;
right = right -> next;
}
}
while (left != nullptr) {
temp -> next = left;
temp = temp -> next;
left = left -> next;
}
while (right != nullptr) {
temp -> next = right;
temp = temp -> next;
right = right -> next;
}
return dummy -> next;
}
ListNode* mergeSort(vector& lists, int start, int end) {
if (start == end)
return lists[start];
int mid = start + (end - start) / 2;
ListNode *left = mergeSort(lists, start, mid);
ListNode *right = mergeSort(lists, mid + 1, end);
return merge(left, right);
}
ListNode* mergeKLists(vector& lists) {
if (lists.size() == 0)
return nullptr;
return mergeSort(lists, 0, lists.size() - 1);
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Hard (56.71%) | 12700 | 625 |
Companies
Given the head
of a linked list, reverse the nodes of the list k
at a time, and return the modified list.
k
is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k
then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Constraints:
- The number of nodes in the list is
n
. 1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1)
extra memory space?
Approach:
Intuition
This code defines a C++ class named Solution
with a public function reverseKGroup
that takes a linked list (ListNode* head
) and an integer k
as parameters. The goal is to reverse every k
nodes in the linked list.
The reverseKGroup
function starts by checking if the input head is null, and if so, returns null. It then defines a tail
pointer that initially points to the head.
Next, the function iterates over k
nodes, updating the tail
pointer accordingly. If there are fewer than k
nodes remaining, it returns the head (no reversal).
The actual reversal is done using a helper function called reverse
, which reverses a segment of the linked list from head
to tail
. It iterates through the segment, reversing the pointers to nodes to achieve the reversal.
After reversing the segment using the reverse
function, the reverseKGroup
function recursively calls itself on the remaining nodes (beyond the reversed segment) with a recursive call reverseKGroup(tail, k)
. The reversed segment’s head is connected to the next reversed segment obtained from the recursive call, and the new head of the reversed portion is returned.
Overall, this code uses a recursive approach to reverse segments of the linked list with a size of k
nodes each.
Approach
The approach of this code involves a recursive algorithm to reverse groups of k
nodes in a linked list. Here’s a breakdown of the approach:
Base Cases:
- If the input head is null, return null (base case for recursion).
- Check if there are at least
k
nodes from the current head. If not, return the head as there are no groups to reverse.
Reversing a Segment of Size
k
:- Use a helper function
reverse
to reverse the segment of the linked list from the current head to thek
th node (represented by thetail
pointer).
- Use a helper function
Recursive Reverse:
- Recursively call
reverseKGroup
for the remaining part of the linked list starting from the node after thetail
(obtained after reversing). This recursive call attempts to reverse the next group ofk
nodes.
- Recursively call
Connecting Reversed Segments:
- Connect the head of the reversed segment (returned by
reverse
function) to the head of the next reversed segment obtained from the recursive call.
- Connect the head of the reversed segment (returned by
Return New Head:
- Return the new head of the reversed portion, which is the head of the first reversed segment.
By recursively reversing groups of k
nodes and appropriately connecting them, the algorithm achieves the goal of reversing every k
nodes in the linked list.
Complexity
The time and space complexity of the provided code can be analyzed as follows:
Time Complexity:
- The time complexity of the
reverse
function is O(k), where k is the number of nodes to reverse in a group. - The
reverseKGroup
function callsreverse
and itself recursively. In the worst case, it may traverse all the nodes in the linked list, and for each group of k nodes, it calls thereverse
function which takes O(k) time. - Therefore, the overall time complexity of the algorithm is O(N), where N is the total number of nodes in the linked list.
- The time complexity of the
Space Complexity:
- The space complexity is determined by the call stack during recursive calls.
- In the worst case, the maximum depth of the recursive call stack would be O(N/k) due to the recursive approach where each group of k nodes is processed.
- Therefore, the space complexity of the algorithm is O(N/k) due to the recursive call stack.
Overall, the algorithm’s time complexity is O(N) and the space complexity is O(N/k), where N is the number of nodes in the linked list and k is the group size for reversing.
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr)
return nullptr;
ListNode* tail = head;
for (int i = 0; i < k; ++i) {
if (tail == nullptr) // Less than k nodes, do nothing
return head;
tail = tail->next;
}
ListNode* newHead = reverse(head, tail);
head->next = reverseKGroup(tail, k);
return newHead;
}
private:
// Reverses [head, tail)
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != tail) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};
Category | Difficulty | Likes | Dislikes |
---|---|---|---|
algorithms | Easy (40.63%) | 4891 | 278 |
Companies
Given two strings needle
and haystack
, return the index of the first occurrence of needle
in haystack
, or -1
if needle
is not part of haystack
.
Example 1:
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.
Example 2:
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104
haystack
andneedle
consist of only lowercase English characters.
Approach:
class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};