# Tag: leetcode-easy

## Find Number with More Than 25 Percent Frequency In Sorted Array

Leetcode Element Appearing More Than 25% In Sorted Array class Solution(object): def findSpecialInteger(self, arr): “”” :type arr: List[int] :rtype: int “”” if len(arr) > 8: return self.getMostFrequentNumberOptimized(arr) return self.getMostFrequentNumber(arr) def getMostFrequentNumber(self, arr): counter = {} for n in arr: if n in counter: counter[n] += 1 else: counter[n] = 1 targetPercent = (len(arr) * 25)//100 for n in counter: if…

## K Weakest Rows in a Matrix

Problem The K Weakest Rows in a Matrix Solution Uses Binary search to count 1s Uses heap to keep k weakest rows It naturally satisfies the condition for weak rows with the same number of soldiers. The smaller index row is processed first and hence any next row would not get pushed to the heap. from heapq import heappushpop, heappush,…

## Number of 1s in a sorted array

Problem Count number of 1s in a sorted array. e.g. [1,1,1,1,0,0,0,0,0,0] Code def countOneBS(row, start, end): if row[start] == 0: return 0 if row[end] == 1: return end – start + 1 # The mid is dependent on the index of start mid = start + (end – start) // 2 # print(“mid=”, mid, “start=”, start, “end=”, end) return countOneBS(row,…

## Palindrome String Check With Non-alphanumeric Characters

class Solution(object): def isPalindrome(self, s): “”” :type s: str :rtype: bool “”” if len(s) < 1: return True start, end = 0, len(s) – 1 while start < end: # Loop till a special char is found while start < end and not s[start].isalnum(): start += 1 # Always keep the check start < end while start < end and…

## Stocks Maximize Profit, Multiple Buy & Sell

class Solution(object): def maxProfit(self, prices): “”” :type prices: List[int] :rtype: int “”” if len(prices) < 2: return 0 minP = prices result = 0 for price in prices: if minP == float(‘inf’): minP = price profit = (price – minP) if profit > 0: result += profit minP = float(‘inf’) minP = min(price, minP) return result Reference https://www.programcreek.com/2014/02/leetcode-best-time-to-buy-and-sell-stock-java/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ Written…

class Solution(object): def maxProfit(self, prices): “”” :type prices: List[int] :rtype: int “”” if len(prices) == 0 or len(prices) == 1: return 0 minP = prices result = 0 for price in prices: # Maintain the maximum profit at each price result = max(result, price – minP) # Maintain the minimum price seen so far minP = min(minP, price) if result…

## Intersection of Two Linked Lists

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def getIntersectionNode(self, headA, headB): “”” :type head1, head1: ListNode :rtype: ListNode “”” lenA, lenB = 0, 0 curA, curB = headA, headB while curA: lenA += 1 curA = curA.next while curB: lenB += 1 curB = curB.next…

## Majority Element in a List

Solution using Moore’s Voting Algorithm class Solution(object): def majorityElement(self, nums): “”” :type nums: List[int] :rtype: int “”” current = nums freq = 1 for i in range(1, len(nums)): if current is None: current = nums[i] freq = 1 continue if nums[i] == current: freq += 1 else: freq -= 1 if freq == 0: current = None return current The…

## Rotate an Array using Constant Space

class Solution(object): def reverse(self, start, end, nums): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 def rotate(self, nums, k): “”” :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. “”” if len(nums) == 0: return nums k = k % len(nums) # reverse the array self.reverse(0,…

## Python Solution: House Robber Problem

class Solution(object): def __init__(self): self.maxVal = 0 self.lookup = {} def rob(self, nums): “”” :type nums: List[int] :rtype: int “”” if len(nums) == 0: return 0 if len(nums) == 1: return nums if len(nums) >= 2: self.lookup = nums self.lookup = max(nums, nums) for index in range(2, len(nums)): # There are two options at each house: choose or not choose…