development

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 […]

Read more
development

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. […]

Read more
development

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=”, […]

Read more
development

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 […]

Read more
development

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[0] 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 […]

Read more
development

Stock Buy-Sell Maximize Profit

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[0] 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 […]

Read more
development

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 […]

Read more
development

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[0] 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 […]

Read more
development

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) […]

Read more
development

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[0] if len(nums) >= 2: self.lookup[0] = nums[0] self.lookup[1] = max(nums[0], nums[1]) for index in range(2, len(nums)): # There are two options at each […]

Read more