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 x and find if there is another value that equals to target−x

				
					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
algorithmsMedium (41.34%)286065520
Tags

Companies

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

 

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Approach:

Intuition:

The Intuition is to iterate through two linked lists representing non-negative integers in reverse order, starting from the least significant digit. It performs digit-wise addition along with a carry value and constructs a new linked list to represent the sum. The process continues until both input lists and the carry value are exhausted. The resulting linked list represents the sum of the input numbers in the correct order.

Explanation:

  1. Create a placeholder node called dummyHead with a value of 0. This node will hold the resulting linked list.
  2. Initialize a pointer called tail and set it to dummyHead. This pointer will keep track of the last node in the result list.
  3. Initialize a variable called carry to 0. This variable will store the carry value during addition.
  4. Start a loop that continues until there are no more digits in both input lists (l1 and l2) and there is no remaining carry value.
  5. Inside the loop:
    • Check if there is a digit in the current node of l1. If it exists, assign its value to a variable called digit1. Otherwise, set digit1 to 0.
    • Check if there is a digit in the current node of l2. If it exists, assign its value to a variable called digit2. Otherwise, set digit2 to 0.
    • Add the current digits from l1 and l2, along with the carry value from the previous iteration, and store the sum in a variable called sum.
    • Calculate the unit digit of sum by taking the modulus (%) of sum by 10. This digit will be placed in a new node for the result.
    • Update the carry variable by dividing sum by 10 and taking the integer division (/) part. This gives us the carry value for the next iteration.
    • Create a new node with the calculated digit as its value.
    • Attach the new node to the tail node of the result list.
    • Move the tail pointer to the newly added node.
    • Move to the next nodes in both l1 and l2, if they exist. If either list is exhausted, set the corresponding pointer to nullptr.
  6. After the loop, obtain the actual result list by skipping the dummyHead node.
  7. Delete the dummyHead node.
  8. Return the resulting list.
				
					class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        int carry = 0;

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int digit1 = (l1 != nullptr) ? l1->val : 0;
            int digit2 = (l2 != nullptr) ? l2->val : 0;

            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;

            ListNode* newNode = new ListNode(digit);
            tail->next = newNode;
            tail = tail->next;

            l1 = (l1 != nullptr) ? l1->next : nullptr;
            l2 = (l2 != nullptr) ? l2->next : nullptr;
        }

        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsHard (38.11%)263952897
Tags

Companies

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Approach:

In simpler terms, you need to find the middle value of the combined, sorted array formed by merging nums1 and nums2. If the combined array has an even number of elements, you should return the average of the two middle values. If it has an odd number of elements, you should return the middle value itself.

Hint:

Think of a brute force approach.
 

I would recommend you, don’t jump directly on solution.

Approach 1: Merge and Sort

  • Create a new array with a size equal to the total number of elements in both input arrays.
  • Insert elements from both input arrays into the new array.
  • Sort the new array.
  • Find and return the median of the sorted array.

Time Complexity

  • In the worst case TC is O((n + m) * log(n + m)).

Space Complexity

  • O(n + m), where ‘n’ and ‘m’ are the sizes of the arrays.

Approach 2: Two-Pointer Method

  • Initialize two pointers, i and j, both initially set to 0.
  • Move the pointer that corresponds to the smaller value forward at each step.
  • Continue moving the pointers until you have processed half of the total number of elements.
  • Calculate and return the median based on the values pointed to by i and j.

Time Complexity

  • O(n + m), where ‘n’ & ‘m’ are the sizes of the two arrays.

Space Complexity

  • O(1).

Approach 3: Binary Search

  • Use binary search to partition the smaller of the two input arrays into two parts.
  • Find the partition of the larger array such that the sum of elements on the left side of the partition in both arrays is half of the total elements.
  • Check if this partition is valid by verifying if the largest number on the left side is smaller than the smallest number on the right side.
  • If the partition is valid, calculate and return the median.

Time Complexity

  • O(logm/logn)

Space Complexity

  • O(1)
				
					class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // Get the sizes of both input arrays.
        int n = nums1.size();
        int m = nums2.size();

        // Merge the arrays into a single sorted array.
        vector<int> merged;
        for (int i = 0; i < n; i++) {
            merged.push_back(nums1[i]);
        }
        for (int i = 0; i < m; i++) {
            merged.push_back(nums2[i]);
        }

        // Sort the merged array.
        sort(merged.begin(), merged.end());

        // Calculate the total number of elements in the merged array.
        int total = merged.size();

        if (total % 2 == 1) {
            // If the total number of elements is odd, return the middle element as the median.
            return static_cast<double>(merged[total / 2]);
        } else {
            // If the total number of elements is even, calculate the average of the two middle elements as the median.
            int middle1 = merged[total / 2 - 1];
            int middle2 = merged[total / 2];
            return (static_cast<double>(middle1) + static_cast<double>(middle2)) / 2.0;
        }
    }
};
				
			

 

CategoryDifficultyLikesDislikes
algorithmsMedium (32.81%)273951626
Tags

Companies

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Approach:

 

LPS0.png

The only tricky thing is that you have to be sure the right substring is returned in expand(). The loop ends only after expanding the range by 1 on both sides, so you have to remove those in the final returned string.

Here we basically choose each centre and try expanding from each and every specific node thus we call expand functionas expand(i,i) and expand(i,i+1) and later we apply two pointers on each node to find the longest palindrome

				
					class Solution {
public:
    string ans = "";
    void expand(string &s , int left ,int right)
    {
        while(left >= 0 &&  right < s.size())
        {
            if(s[left] != s[right])
                break;
            left--,right++;
        }
        if(ans.size() < right - left )
            ans = s.substr(left + 1 , right - left - 1);
    }
    string longestPalindrome(string s) {
        for(int i = 0 ; i < s.size() ; i++)
        {
            expand(s , i , i);
            expand(s , i , i+1);
        }
        return ans;
    }
};
				
			
CategoryDifficultyLikesDislikes
algorithmsMedium (16.78%)389212058
Tags

Companies

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

  1. Read in and ignore any leading whitespace.
  2. Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
  3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
  4. Convert these digits into an integer (i.e. "123" -> 123"0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
  5. If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
  6. Return the integer as the final result.

Note:

  • Only the space character ' ' is considered a whitespace character.
  • Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.

 

Example 1:

Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.

Example 2:

Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.

Example 3:

Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
             ^
The parsed integer is 4193.
Since 4193 is in the range [-231, 231 - 1], the final result is 4193.

 

Constraints:

  • 0 <= s.length <= 200
  • s consists of English letters (lower-case and upper-case), digits (0-9), ' ''+''-', and '.'.

Approach:

Intuition

We can solve this problem using String.

Approach

We can easily understand the approach by seeing the code which is easy to understand with comments.

Complexity

  • Time complexity:

Time Complexity : O(logN), Since we are going through the entire number digit by digit, the time complexity should be O(log10N). The reason behind log10 is because we are dealing with integers which are base 10.

  • Space complexity:

Space Complexity : O(1), We are not using any data structure for interim operations, therefore, the space complexity is O(1).

				
					
/*

    Time Complexity : O(logN), Since we are going through the entire number digit by digit, the time complexity
    should be O(log10N). The reason behind log10 is because we are dealing with integers which are base 10.

    Space Complexity : O(1), We are not using any data structure for interim operations, therefore, the space
    complexity is O(1).

    Solved using String.

*/

class Solution {
public:
    int myAtoi(string s) {
        int len = s.size();
        double num = 0;
        int i=0;
        while(s[i] == ' '){
            i++;
        }
        bool positive = s[i] == '+';
        bool negative = s[i] == '-';
        positive == true ? i++ : i;
        negative == true ? i++ : i;
        while(i < len && s[i] >= '0' && s[i] <= '9'){
            num = num*10 + (s[i]-'0');
            i++;
        }
        num = negative ? -num : num;
        cout<<num<<endl;
        num = (num > INT_MAX) ? INT_MAX : num;
        num = (num < INT_MIN) ? INT_MIN : num;
        cout<<num<<endl;
        return int(num);
    }
};
				
			
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:

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 (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
algorithmsEasy (63.25%)202131884
Tags

Companies

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

 

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

Approach:

Intuition

Recursion allows you to push all tasks to subsequent calls. All you need to understand at the current step is whether one of your lists has ended, and if not, then add at least of the elements to the result!

Complexity

  • Time complexity:
    O(min(len(list1),len(list2)))O(min(len(list1), len(list2))) because the job finishes when we reach the end of one of the lists
				
					/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr){
            return list2;
        }
        if (list2 == nullptr){
            return list1;
        }
        if (list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else{
            list2->next = mergeTwoLists(list2->next, list1);
            return list2;
        }
    }
};
				
			
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.
				
					class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) {
            return nullptr;
        }
        return mergeKListsHelper(lists, 0, lists.size() - 1);
    }
    
    ListNode* mergeKListsHelper(vector<ListNode*>& lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (start + 1 == end) {
            return merge(lists[start], lists[end]);
        }
        int mid = start + (end - start) / 2;
        ListNode* left = mergeKListsHelper(lists, start, mid);
        ListNode* right = mergeKListsHelper(lists, mid + 1, end);
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                curr->next = l1;
                l1 = l1->next;
            } else {
                curr->next = l2;
                l2 = l2->next;
            }
            curr = curr->next;
        }
        
        curr->next = l1 ? l1 : l2;
        
        return dummy->next;
    }
};