Merge k Sorted Lists - Leetcode 23 - Python

Merge k Sorted Lists

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: []

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or len(lists) == 0 :
            return None
        while len(lists) > 1 :
            ml = []
            
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if (i+1) <len(lists) else None
                ml.append(self.mergeTwoLists(l1,l2))
            lists = ml
        return lists[0]
    
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        d = ListNode()
        p = d
        
        while l1 and l2 :
            if l1.val < l2.val :
                p.next = l1
                l1 = l1.next 
            else :
                p.next = l2
                l2 = l2.next
            
            p = p.next
            
            
        if l1 :
            p.next = l1
        else :
            p.next = l2
            
        return d.next

Explaination :

Comments

Leetcode 424. Longest Repeating Character Replacement. Python (Sliding Window)

424 . Longest Repeating Character Replacement You are given a string s and an integer k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations . Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. Constraints: 1 <= s.length <= 10 5 s consists of only uppercase English letters. 0 <= k <= s.length Solution : class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0 ...

Leetcode 371. Sum of Two Integers. C++ / Java

371 . Sum of Two Integers Given two integers a and b , return the sum of the two integers without using the operators + and - . Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5 Constraints: -1000 <= a, b <= 1000 Solution : C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java : class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Two Sum - Leetcode 1 - HashMap - Python

1. Two Sum 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 class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashmap = {} # val : index for i,n in enumerate(nums): diff = target - n if diff in hashmap: return [hashmap[diff],i] hashmap[n]=i return Explained :

LEETCODE SOLUTIONS

Search This Blog