LeetCode in Python - Day 1

1. https://leetcode.com/problems/two-sum/
2. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
3. https://leetcode.com/problems/plus-one/
4. https://leetcode.com/problems/move-zeroes/

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