حل سوالات استخدامی سایت leetcode.com

Task: No. 16. 3Sum Closest #medium

Condition:
Given an integer array nums of length n and an integer target, find the three integers in nums whose sum is closest to the target. Returns the sum of three integers. You can assume that each input will have exactly one solution.

Solution:

    def threeSumClosest(self, num, target):
        num.sort()
        result = num[0] + num[1] + num[2]
        for i in range(len(num) - 2):
            j, k = i+1, len(num) - 1
            while j < k:
                sum = num[i] + num[j] + num[k]
                if sum == target:
                    return sum
                
                if abs(sum - target) < abs(result - target):
                    result = sum
                
                if sum < target:
                    j += 1
                elif sum > target:
                    k -= 1
                else:
                    return result
            
        return result

Explanation:
Sort an array:

First we sort the num array. This will allow us to use two pointers to find the closest sum.
Initializing the result:

We initialize the result variable with the sum of the first three elements of the sorted array. This will be our starting closest amount.
Traversing the array:

We use a for loop to iterate through the array. For each element we use two pointers j and k:
j starts immediately after the current element i.
k starts from the end of the array.
Two pointers:

Inside the while loop, while j is less than k, we calculate the sum of the elements num[i], num[j] and num[k].
If sum equals target, then we return sum since we found an exact match.
Result update:

If the current sum sum is closer to target than the previous closest sum result, update result.
Pointer shift:

If sum is less than target, move pointer j to the right to increase the sum.
If sum is greater than target, shift pointer k to the left to decrease the sum.
Return result:

After completing all iterations, we return result, which will contain the sum of three numbers closest to target.
Time and space complexity:
Time complexity: O(n^2), where n is the length of the array. Sorting takes O(n log n) and the basic algorithm with two pointers runs in O(n^2).
Space complexity: O(1) since we only use a few additional variables, and do not use additional memory depending on the size of the input data.

#interview #LeetCode

🆔 @Python4all_pro

حل سوالات استخدامی سایت leetcode.com

Task: No. 17. Letter Combinations of a Phone Number #medium

Condition:
Given a string containing the numbers 2 to 9 inclusive, return all possible combinations of letters that the number can represent. Return the answer in any order. The correspondence between numbers and letters (as on telephone buttons) is given below. Note that 1 does not match any letters.

Solution:

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        self.dfs(nums, [], res)
        return res
    
    def dfs(self, nums, path, res):
        res.append(path)
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[i+1:], path + [nums[i]], res)

Explanation:
Sorting:

First we sort the nums array. Sorting makes it easy to handle duplicates because similar items will be placed next to each other.
Recursive dfs method:

The dfs method is used to recursively construct all possible subsets. In dfs, path represents the current subset, and res is a list of all subsets.
Adding a subset to the result:

At each level of recursion, we add the current subset of path to the result of res.
Handling duplicates:

Before continuing the recursion, we check whether the current element nums[i] is a duplicate of the previous element. If so, skip it to avoid adding identical subsets to res.
Recursive construction of subsets:

For each element in nums, starting at the current index, we call dfs on the next elements of the array (nums[i+1:]). This means that we consider subsets that include the current element, and continue to build subsets without the current element.
Path (path) and compartment (nums):

Each time dfs is called, a new subset is created by adding the current element to path. This new list is then passed to the next level of recursion, allowing all possible subsets to be constructed.
Time and space complexity:
Time complexity: O(2^n), where n is the number of elements in nums. This is because there are 2^n subsets for an array of n elements.
Space complexity: O(2^n * n), since each of the 2^n possible subsets may require up to n elements to store.


#interview #LeetCode

🆔 @Python4all_pro