Leetcode with dani

#Q21 #leet_codeQ1249 Medium title. Minimum Remove to Make Valid Parentheses
Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.


Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.
Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"
Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.


Constraints:

1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.

Selection sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
      
        # Assume the current position holds
        # the minimum element
        min_idx = i
        
        # Iterate through the unsorted portion
        # to find the actual minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
              
                # Update min_idx if a smaller element is found
                min_idx = j
        
        # Move minimum element to its
        # correct position
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

insertion sort

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

bubble sort

def bubbleSort(arr):
    n = len(arr)
    
    # Traverse through all array elements
    for i in range(n):
        swapped = False

        # Last i elements are already in place
        for j in range(0, n-i-1):

            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if (swapped == False):
            break

this question is asked by amazon in interviews frequently

https://leetcode.com/problems/the-kth-factor-of-n/?envType=study-plan-v2&envId=amazon-spring-23-high-frequency

#Q21 #leet_codeQ16 #3Sum_Closest
Medium

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.



Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).


Constraints:

3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104

after solving 3 sum try to solve the next question

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        list1 = []
        for i in range(len(nums)-1,-1,-1):
            j = i - 1
            left =0
            if (i>1 and i!=(len(nums)-1) and nums[i]==nums[i+1]):
                        continue
            while(j>-1 and left<=i-2 and j!=left):
                total = nums[left] + nums[i] + nums[j]
                if ( total)== 0:
                    list1.append([nums[left],nums[i],nums[j]])
                    left+=1
                    while(left<j and nums[left]==nums[left-1]):
                        left+=1
                elif total > 0:
                    j-=1
                else:
                    left+=1
        return list1

https://youtu.be/jzZsG8n2R9A?si=s8jIL0Yg1LiGfwoC

✨ Master Python Division: int(x / y) vs. x // y ✨

Ever wonder about the difference between int(x / y) and x // y in Python? Let’s break it down! 🧠👇

int(x / y):
- Performs regular division first (x / y), giving a floating-point result.
- Then, truncates the result to an integer using int(), removing the decimal part.
- Example:
- int(7 / 3) ➡️ 2 (since 7 / 3 ≈ 2.3333, truncates to 2).
- int(-7 / 3) ➡️ -2 (since -7 / 3 ≈ -2.3333, truncates to -2).

x // y (Floor Division):
- Directly performs floor division, rounding down to the nearest integer.
- Example:
- 7 // 3 ➡️ 2 (largest integer ≤ 2.3333).
- -7 // 3 ➡️ -3 (largest integer ≤ -2.3333).

Key Differences:
- Rounding:
- int(x / y) truncates towards zero.
- x // y rounds down towards negative infinity.
- Negative numbers:
- For positive results, both are the same.
- For negative results, int(x / y) truncates, but x // y rounds down.

Example with Negative Numbers:
- int(-7 / 3) ➡️ -2
- -7 // 3 ➡️ -3

https://t.me/+m835nLa3A0c2MjBk join our discussion group

did you solve this problem?

In my opinion, if you're preparing for an interview and have no enough time left, it’s best not to spend more than 45 minutes on a single problem. Instead, I believe you should focus on understanding different patterns and concepts. This approach can help you become more versatile and better equipped to tackle various questions during the interview. what do you think?

#Q20 #leet_codeQ15 Medium title. 3Sum
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.

🚀 Explore Palindrome Challenges with the Two-Pointer Technique!🧑‍💻

Palindromes are a classic problem type that can be efficiently tackled using the two-pointer technique. Whether you're just starting or looking to refine your skills, these questions will help you master this approach. Check out these palindrome problems:

1.Valid Palindrome
🔗 [Link](https://leetcode.com/problems/valid-palindrome/)
Description: Determine if a string is a palindrome, considering only alphanumeric characters and ignoring cases.

2. Valid Palindrome II
🔗 [Link](https://leetcode.com/problems/valid-palindrome-ii/)
Description: Can the string become a palindrome by deleting just one character?

3. Palindrome Linked List
🔗 [Link](https://leetcode.com/problems/palindrome-linked-list/)
Description: Check if a singly linked list is a palindrome using two pointers and a bit of list manipulation.

4. Longest Palindromic Substring
🔗 [Link](https://leetcode.com/problems/longest-palindromic-substring/)
Description: Find the longest palindromic substring in a given string, with pointers expanding from each character.

5. Palindromic Substrings
🔗 [Link](https://leetcode.com/problems/palindromic-substrings/)
Description: Count how many palindromic substrings are present in the string using two pointers.

6. Shortest Palindrome.
🔗 [Link](https://leetcode.com/problems/shortest-palindrome/)
Description: Find the shortest palindrome by adding characters to the start of the string.

7. Palindrome Partitioning
🔗 [Link](https://leetcode.com/problems/palindrome-partitioning/)
Description: Partition a string into all possible palindromic substrings.

8. Palindrome Pairs
🔗 [Link](https://leetcode.com/problems/palindrome-pairs/)
Description: Given a list of words, find all pairs of distinct indices that form palindromes.

Ready to boost your problem-solving skills? Dive into these problems, practice your two-pointer technique, and ace those palindrome challenges! 💥

Happy Coding! 💻💡

▎1. 3Sum

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
    return result


▎2. Minimum Window Substring

from collections import Counter

def minWindow(s, t):
    if not t or not s:
        return ""
   
    dict_t = Counter(t)
    required = len(dict_t)
   
    l, r = 0, 0
    formed = 0
    window_counts = {}
   
    ans = float("inf"), None, None
   
    while r < len(s):
        character = s[r]
        window_counts[character] = window_counts.get(character, 0) + 1
       
        if character in dict_t and window_counts[character] == dict_t[character]:
            formed += 1
       
        while l <= r and formed == required:
            character = s[l]
           
            if r - l + 1 < ans[0]:
                ans = (r - l + 1, l, r)
           
            window_counts[character] -= 1
            if character in dict_t and window_counts[character] < dict_t[character]:
                formed -= 1
           
            l += 1
       
        r += 1
   
    return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]


▎3. Fruit Into Baskets

def totalFruits(fruits):
    left, right = 0, 0
    basket = {}
    max_fruits = 0
   
    while right < len(fruits):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
       
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
       
        max_fruits = max(max_fruits, right - left + 1)
        right += 1
   
    return max_fruits

1. 3Sum (Hard) 
   Answer: The solution involves sorting the array and using a two-pointer technique to find triplets that sum to zero. The time complexity is O(n^2).


2. Minimum Window Substring (Hard) 
   Answer: Use a sliding window approach to maintain a count of characters and expand/shrink the window until the minimum substring is found. The time complexity is O(n).

3. Fruit Into Baskets (Easy) 
   Answer: Utilize a sliding window to track the types of fruits and their counts, ensuring you only have two types at any time. The maximum length of the window gives the answer. The time complexity is O(n).

Understanding the constraints, time complexity is key to solving LeetCode problems effectively. If you find these concepts confusing, don’t worry , you’re not alone!.

this might help you to undestand the constraints

3. Fruit Into Baskets (Easy)
Description: You are visiting a farm and have a basket that can hold at most two types of fruits. You want to maximize the number of fruits you collect. Given an array of integers representing the types of fruits in a row, find the maximum number of fruits you can collect in one basket.
- Example: For input [1,2,1], the maximum number of fruits collected is 3.

2. Minimum Window Substring (Hard)
Description: Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return an empty string.
- Example: For s = "ADOBECODEBANC" and t = "ABC", the minimum window is "BANC".