day2(5july)

 121. 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.

wrong approach

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprices=min(prices)
        maxxy=max(prices)
        maxprice=minprices
        index=prices.index(minprices)
        if index==(len(prices)-1):
            if(len(prices))>=3:
                for i in range(len(prices)-1)):
                    if prices[i]<maxxy:
                        minprices=prices[i]
                result=maxxy-minprices
                return result
            return 0
        else:
            for i in range(index+1,len(prices)):
                if prices[i]>maxprice:
                    maxprice=prices[i]
            result=maxprice-minprices
            return result



correct approach
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minprice=float('inf')
        max_profit=0
        for i in prices:
            if i<minprice:
                minprice=i
            profit=i-minprice
            if profit>max_profit:
                max_profit=profit
        return max_profit
1394. Find Lucky Integer in an Array
Given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value.
Return the largest lucky integer in the array. If there is no lucky integer return -1.
 
Example 1:
Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.
Example 2:
Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.
Example 3:
Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.
from collections import Counter
class Solution:
    def findLucky(self, arr: List[int]) -> int:
        maxxy=-1
        frequency = Counter(arr)
        for key, value in frequency.items():
            if key==value:
                if key>maxxy:
                    maxxy=key
                    
        return maxxy

912. Sort an Array
Medium
Topics
Companies
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
 
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.

ArrayDivide and ConquerSortingHeap (Priority Queue)Merge SortBucket SortRadix Sort
Counting Sort