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.

CategoryDifficultyLikesDislikes
algorithmsEasy (50.82%)521991712
Tags

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).
    For each element, we try to find its complement by looping through the rest of the array which takes O(n)O(n) time. Therefore, the time complexity is O(n2)O(n^2).

  • Space complexity: 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<int> twoSum(vector<int>& 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
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (27.86%)114651918
Tags

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:

    1. 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].
    2. 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<std::vector<bool>> dp(m+1, std::vector<bool>(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];
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsEasy (59.53%)12528738
Tags

Companies

Roman numerals are represented by seven different symbols: IVXLCD 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:

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

  2. The variable ans is initialized to 0. This variable will accumulate the final integer value of the Roman numeral string.

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

  4. 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<char, int> 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;
    }
}
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (33.37%)287162578
Tags

Companies

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != ji != 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:

  1. Sort the input array
  2. Initialize a set to store the unique triplets and an output vector to store the final result
  3. Iterate through the array with a variable i, starting from index 0.
  4. Initialize two pointers, j and k, with j starting at i+1 and k starting at the end of the array.
  5. 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.
  6. If the sum is less than 0, increment j. If the sum is greater than 0, decrement k.
  7. After the while loop, iterate through the set and add each triplet to the output vector.
  8. Return the output vector
				
					//Optimized Approach - O(n^2 logn + nlogn) - o(n^2 logn) time and O(n) space
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target = 0;
        sort(nums.begin(), nums.end());
        set<vector<int>> s;
        vector<vector<int>> 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;
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsEasy (53.34%)1289317009
Tags

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 * 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:

  1. 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.
  2. 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.
  3. 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<int>& 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;
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (58.72%)17309903
Tags

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

  1. Return Type: it returns nothing
  2. 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:
  1. 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:
  1. 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<char, vector<char>> 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<string> &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<string> letterCombinations(string digits)
    {
        DPSolver;
        // remove all ones
        digits.erase(remove(digits.begin(), digits.end(), '1'), digits.end());
        vector<string> ans;
        backtracking(0, digits, "", ans);
        return ans;
    }

};
				
			
CategoryDifficultyLikesDislikes
algorithmsEasy (40.19%)222791501
Tags

Companies

Given a string s containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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:

  1. Initialize an empty stack.

  2. Traverse the input string character by character.

  3. If the current character is an opening bracket (i.e., ‘(‘, ‘{‘, ‘[‘), push it onto the stack.

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

  5. 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), 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), 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<char> 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
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (51.04%)18425658
Tags

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 exceed 104.

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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<ListNode*>& 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<ListNode*>& lists) {
        if (lists.size() == 0)
            return nullptr;
        return mergeSort(lists, 0, lists.size() - 1);
    }
};
				
			

 

CategoryDifficultyLikesDislikes
algorithmsHard (56.71%)12700625
Tags

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:

  1. 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.
  2. 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 kth node (represented by the tail pointer).
  3. 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.
  4. 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.
  5. 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:

  1. 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.
  2. 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;
  }
};
				
			

 

CategoryDifficultyLikesDislikes
algorithmsEasy (40.63%)4891278
Tags

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 and needle consist of only lowercase English characters.

Approach:

Intuition

Approach

Complexity

  • Time complexity:
    O(n*m)

  • Space complexity:
    O(1)

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