## 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 <= 10`

^{4}`-10`

^{9}<= nums[i] <= 10^{9}`-10`

^{9}<= target <= 10^{9}**Only one valid answer exists.**

**Follow-up: **Can you come up with an algorithm that is less than `O(n`

time complexity?^{2})

## 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(n_{2})$.

For each element, we try to find its complement by looping through the rest of the array which takes $O(n)$ time. Therefore, the time complexity is $O(n_{2})$.Space complexity: $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 before`V`

(5) and`X`

(10) to make 4 and 9.`X`

can be placed before`L`

(50) and`C`

(100) to make 40 and 90.`C`

can be placed before`D`

(500) and`M`

(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 character`s[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 condition`m[s[i]] < m[s[i+1]]`

is true. In this case, we subtract the value of the current character from`ans`

.`ans -= m[s[i]];`

`ans -= m['I'];`

`ans -= 1;`

`ans`

becomes -1.When

`i`

is 1, the current character`s[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 to`ans`

.`ans += m[s[i]];`

`ans += m['X'];`

`ans += 10;`

`ans`

becomes 9.

**For the example “XI”:**When

`i`

is 0, the current character`s[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 condition`m[s[i]] < m[s[i+1]]`

is false. In this case, we add the value of the current character to`ans`

.`ans += m[s[i]];`

`ans += m['X'];`

`ans += 10;`

`ans`

becomes 10.When

`i`

is 1, the current character`s[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 to`ans`

.`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`

`-10`

^{5}<= nums[i] <= 10^{5}

## 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 first`k`

elements of`nums`

contain the unique elements in the order they were present in`nums`

initially. The remaining elements of`nums`

are not important as well as the size of`nums`

. - 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 * 10`

^{4}`-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 element`nums[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 at`nums[i]`

, and then increment`j`

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 <= 10`

^{4}`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)$, 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)$, 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 <= 10`

^{4}`0 <= lists[i].length <= 500`

`-10`

^{4}<= lists[i][j] <= 10^{4}`lists[i]`

is sorted in**ascending order**.- The sum of
`lists[i].length`

will not exceed`10`

.^{4}

## 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 the`k`

th node (represented by the`tail`

pointer).

- Use a helper function
**Recursive Reverse**:- Recursively call
`reverseKGroup`

for the remaining part of the linked list starting from the node after the`tail`

(obtained after reversing). This recursive call attempts to reverse the next group of`k`

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 calls`reverse`

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 the`reverse`

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 <= 10`

^{4}`haystack`

and`needle`

consist of only lowercase English characters.

## Approach:

` ````
```class Solution {
public:
int strStr(string haystack, string needle) {
return haystack.find(needle);
}
};