Leetcode with dani

You are given a sorted array nums of size n and an integer target. 
Your task is to find the pair of numbers in the array whose sum is less than or equal to the target and has the largest possible sum.

Return the maximum sum of such a pair. If no valid pair exists, return -1.

Example 1:
Input: nums = [2, 3, 5, 8, 13], target = 10
Output: 10
 l
[2, 3, 5, 8, 13],
          r
[7,8 , 10]
Explanation: The pair (2, 8) has a sum of 10, which is the largest possible sum less than or equal to 10.

Example 2:
Input: nums = [1, 1, 1, 1], target = 1
Output: -1
Explanation: No pair has a sum less than or equal to 1.

Constraints:
1<=n<=10⁵
Nums  is sorted in non-decreasing order.



def targetSum(nums , target):
    left = 0
    max_ = -1
    right = len(nums)-1
    while left < right:
        sum = nums[left] + nums[right]
        if sum == target:
            return sum
        elif sum > target:
            right -=1
        elif sum < target:
            left += 1
            max_ = max(max_,sum)
    return max_

You are given a 0-indexed integer array nums.
Swaps of adjacent elements are able to be performed on nums.
A valid array meets the following conditions:
    The largest element (any of the largest elements if there are multiple) is at the rightmost position in the array.
    The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.
Return the minimum swaps required to make nums a valid array.
 
Example 1:
Input: nums = [3,4,5,5,3,1]
Output: 6
Explanation: Perform the following swaps:
- Swap 1: Swap the 3rd and 4th elements, nums is then [3,4,5,3,5,1].
- Swap 2: Swap the 4th and 5th elements, nums is then [3,4,5,3,1,5].
- Swap 3: Swap the 3rd and 4th elements, nums is then [3,4,5,1,3,5].
- Swap 4: Swap the 2nd and 3rd elements, nums is then [3,4,1,5,3,5].
- Swap 5: Swap the 1st and 2nd elements, nums is then [3,1,4,5,3,5].
- Swap 6: Swap the 0th and 1st elements, nums is then [1,3,4,5,3,5].
It can be shown that 6 swaps is the minimum swaps required to make a valid array.

Example 2:
Input: nums = [9]
Output: 0
Explanation: The array is already valid, so we return 0.

    
          
 
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

The length of the subarray is k, and
All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions
Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.
 

Constraints:

1 <= k <= nums.length <= 105
1 <= nums[i] <= 105

"""

Question Description
    Given an input string s, reverse the order of the words.

    A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

    Return a string of the words in reverse order concatenated by a single space.

    Note that s may contain leading or trailing spaces or multiple spaces between two words. 
    The returned string should only have a single space separating the words. Do not include any extra spaces.



    Example 1:

    Input: s = "the sky is blue"
    Output: "blue is sky the"
    Example 2:

    Input: s = "  hello world  "
    Output: "world hello"
    Explanation: Your reversed string should not contain leading or trailing spaces.
    Example 3:

    Input: s = "a good   example"
    Output: "example good a"
    Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
 

Constraints:

    1 <= s.length <= 104
    s contains English letters (upper-case and lower-case), digits, and spaces ' '.
    There is at least one word in s.
    
    
    "a good   example"
["a","good","example"]
      L  R
 
 
 [example,"good","a"]


"""

#will s will split
#variables left->0 rght ->len(splited)-1
#will have  a while l<L    left+=1 righ-=1 


def revercing_word(s):
    words=[] 
    for word in s.split(" "):
        if word:
            words.append(word)
    
    left=0
    right=len(words)-1
    
    
    while left<right:
        words[left],words[right]= words[right],words[left]
        left+=1
        right-=1
        
    return " ".join(words)
print(revercing_word("hello world"))

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

 

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
 

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

Today's Interview Question
You are given a string s, which contains stars *.

In one operation, you can:

Choose a star in s.
Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.

Note:

The input will be generated such that the operation is always possible.
It can be shown that the resulting string will always be unique.


Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

Constraints:

1 <= s.length <= 10**5
s consists of lowercase English letters and stars *.
The operation above can be performed on s.

def fun(s):
    stack = []
    for c in s:
        if c != "*":
            stack.append(c)
        else:
            stack.pop()
    return "".join(stack) 
print(fun("erase*****"))

result = []
for char in string:
    result.append(char)
final_string = ''.join(result)

"""
Given an array of integer arrays arrays where each arrays[i] is sorted in strictly increasing order, 
return an integer array representing the longest common subsequence among all the arrays.
A subsequence is a sequence that can be derived from another sequence by deleting some elements 
(possibly none) without changing the order of the remaining elements.
 
Example 1:
Input: arrays = [[1,3,4],
                 [1,4,7,9]]
Output: [1,4]
Explanation: The longest common subsequence in the two arrays is [1,4].

Example 2:
Input: arrays = [[2,3,6,8],
                 [1,2,3,5,6,7,10],
                 [2,3,4,6,9]]
Output: [2,3,6]
Explanation: The longest common subsequence in all three arrays is [2,3,6].

Example 3:
Input: arrays = [[1,2,3,4,5],
                 [6,7,8]]
Output: []
Explanation: There is no common subsequence between the two arrays.
"""

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized.
Return the maximized sum.

Example 1:

Input: nums = [1,4,3,2]
Output: 4

Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.
Example 2:

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.
1 2 2 5 6 6


Constraints:

1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

238. Product of Array Except Self  
Difficulty: Medium  

Problem:  
Given an integer array nums, return an array answer such that answer[i] is the product of all elements of nums except nums[i].  

Conditions:  
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.  
- Your algorithm must run in O(n) time and must not use the division operation.  

Examples:  
Input: nums = [1,2,3,4]  
Output: [24,12,8,6]  

Input: nums = [-1,1,0,-3,3]  
Output: [0,0,9,0,0]  

Constraints:  
2 <= nums.length <= 10^5  
-30 <= nums[i] <= 30  

Can you solve it?

nums = [2,0,2,1,1,0]

[0,0,1,1,2,2]

nums = [2,0,1]

[0,1,2]

Input: 
maze = [
  [0,0,1,0,0], 
  [0,0,0,0,0], 
  [0,0,0,1,0], 
  [1,1,0,1,1], 
  [0,0,0,0,0]
], 
start = [0,4], 
destination = [4,4]

Output: true

Input:
maze = [
  [0,0,1,0,0], 
  [0,0,0,0,0], 
  [0,0,0,1,0], 
  [1,1,0,1,1], 
  [0,0,0,0,0]
], 
start = [0,4], 
destination = [3,2]

Output: false

Input:
maze = [
  [0,0,0,0,0], 
  [1,1,0,0,1], 
  [0,0,0,0,0], 
  [0,1,0,0,1], 
  [0,1,0,0,0]
], 
start = [4,3], 
destination = [0,1]

Output: false

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]

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

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

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