DEV Community: SaiPavan Seelamsetty

Insertion Sort - Python

SaiPavan Seelamsetty — Mon, 04 Apr 2022 05:05:10 +0000

def insertionSort(array):
    # Write your code here.
    for i in range(1,len(array)):
        j=i
        while j>0 and array[j]<array[j-1]:
            swap(j,j-1,array)
            j-=1
    return array        
def swap(i,j,array):
    array[i],array[j]=array[j],array[i]

#TC=O(n^2)  SC = O(1)  - Saipavan Seelamsetty

Search in Rotated Sorted Array - Python

SaiPavan Seelamsetty — Sat, 26 Mar 2022 07:18:42 +0000

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

https://leetcode.com/problems/search-in-rotated-sorted-array/

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #TC=O(log n)
        s=0
        e=len(nums)-1
        while s<=e:
            mid=(s+e)//2
            if nums[mid]==target:
                return mid
           #left-line
            if nums[s]<=nums[mid]:
                if target>=nums[s] and target<=nums[mid]:
                    e=mid-1
                else:
                    s=mid+1
            else:
                if target>=nums[mid] and target<=nums[e]:
                    s=mid+1
                else:
                    e=mid-1
        return -1

Find First and Last Position of Element in Sorted Array - Python

SaiPavan Seelamsetty — Sat, 26 Mar 2022 06:30:13 +0000

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

    def searchRange(self, numbers: List[int], target: int) -> List[int]:
        result=[-1,-1]
        l=0
        h=len(numbers)-1
        while l<=h:
            mid=(l+h)//2
            if target>numbers[mid]:
                l=mid+1
            elif target<numbers[mid]:
                h=mid-1
            else:
                result[0]=mid
                h=mid-1
        l=0
        h=len(numbers)-1
        while l<=h:
            mid=(l+h)//2
            if target>numbers[mid]:
                l=mid+1
            elif target<numbers[mid]:
                h=mid-1
            else:
                result[1]=mid
                l=mid+1
        return result

LeetCode in Python - Day 1

SaiPavan Seelamsetty — Fri, 25 Mar 2022 17:25:22 +0000

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.

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.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #BruteForce

        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j]==target:
                    return [i,j]
        return [-1,-1]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #optimal---->TC O(N)----->SC=O(N)
        pair_check={}
        count=0
        for i in range(len(nums)):
            b=target-nums[i]
            if b  in pair_check:
                return[pair_check[b],i]
            else:
                pair_check[nums[i]]=i
        return []

2.Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 105
0 <= prices[i] <= 104

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #TC--->O(N)  SC--->O(1)
        buy=prices[0]
        profit=0
        for i in range(1,len(prices)):
            diff=prices[i]-buy
            buy=min(buy,prices[i])
            profit=max(profit,diff)
        return profit

3. Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].
Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].
Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

1 <= digits.length <= 100
0 <= digits[i] <= 9
digits does not contain any leading 0's.

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        #TC--->O(N)  SC---->O(1)
        dig_len=len(digits)
        for i in reversed(range(dig_len)):
            digits[i]+=1
            if digits[i]<10:
                return digits
            else:
                digits[i]=0
        digits.insert(0,1)
        return digits

4. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:

Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        #TC=O(N) SC=O(1)
        """
        Do not return anything, modify nums in-place instead.
        """
        prev_index=0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[i],nums[prev_index]=nums[prev_index],nums[i]
                prev_index+=1

Appreciate your feedback for Improvements by Saipavan Seelamsetty

[Leetcode]1552. Magnetic Force Between Two Balls - Python Solution

SaiPavan Seelamsetty — Tue, 22 Mar 2022 05:13:00 +0000

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.
Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

n == position.length
2 <= n <= 105
1 <= position[i] <= 109
All integers in position are distinct.
2 <= m <= position.length

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        position.sort()
        start=0
        end=position[-1]
        n=len(position)
        ans=0
        while start<=end:
            mid=(start+end)//2
            if(self.gapisenough(position,mid,m)):
                ans=mid
                start=mid+1
            else:
                end=mid-1
        return ans
    def gapisenough(self,position,mid,m):
        initial=1
        prev=position[0]
        for i in range(1,len(position)):
            if(position[i]-prev>=mid):
                initial+=1
                prev=position[i]
                if(initial==m):
                    return True
        if(initial<m):
            return False

[Leetcode]74. Search a 2D Matrix - Python Solution

SaiPavan Seelamsetty — Tue, 22 Mar 2022 04:08:07 +0000

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n=len(matrix)*len(matrix[0])
        start=0
        end=n-1
        while start<=end:
            mid=(start+end)//2
            row=mid//len(matrix[0])
            column=mid%len(matrix[0])
            if matrix[row][column]==target:
                return True
            elif matrix[row][column]>target:
                end-=1
            else:
                start+=1
        return False        

##