Leetcode 153. Find Minimum in Rotated Sorted Array. Python

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

class Solution:
    def findMin(self, n: List[int]) -> int:
        ans = n[0]
        l, r = 0, len(n)-1
        
        while l <= r :
            
            #already sorted
            if n[l] < n[r]:
                ans = min(ans,n[l])
                break
                
            #mid trick
            m = (l+r)//2
            ans = min(ans, n[m])
            if n[m] >= n[l]:
                l = m+1
            else:
                r = m-1
        
        return ans

Explaination :

Comments

May-6 2020 Challenge

6. Majority Element Given an array of size n , find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1,1,2,2] Output: 2 Solution in Java class Solution { public int majorityElement(int[] num) { int m = num[0], cnt= 1; for (int i = 1; i < num.length; i++) { if (cnt == 0) { m= num[i]; cnt = 1; } else if (num[i] == m) { cnt++; } else cnt--; } return m;...

Leetcode 424. Longest Repeating Character Replacement. Python (Sliding Window)

424 . Longest Repeating Character Replacement You are given a string s and an integer k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations . Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. Constraints: 1 <= s.length <= 10 5 s consists of only uppercase English letters. 0 <= k <= s.length Solution : class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0 ...

Longest Substring Without Repeating Characters - Leetcode 3 - Python

Given a string s, find the length of the longest substring without repeating characters. class Solution: def lengthOfLongestSubstring(self, s: str) -> int: charSet = set() left = 0 ans = 0 for right in range(len(s)): while s[right] in charSet: charSet.remove(s[left]) left+=1 charSet.add(s[right]) ans = max(ans, right-left+1) return ans Explained :

LEETCODE SOLUTIONS

Search This Blog