Tag: algorithms

Time Complexity of a Memoized Algorithm

The memoization eliminated duplicate calls to a function. A memoized implementation of Fibonacci code is as follows: package complexity import “fmt” var mem map[int]int func fibo(count int) int { if count == 0 || count == 1 { return count } if mem[count] != -1 { return mem[count] } s := fibo(count-1) + fibo(count-2) mem[count]…

K-Messed Array Sort: Python Solution

K-Messed Array Sort Given an array of integers arr where each element is at most k places away from its sorted position Solution from Queue import PriorityQueue def sort_k_messed_array(arr, k): kheap = PriorityQueue() result = [] for num in arr: kheap.put(num, ‘num’) if kheap.qsize() == (k + 1): item = kheap.get() result.append(item) while not kheap.empty():…

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…

Difference between Increasing & Non-Decreasing Order

Let’s take an array for example: int arr[] = {1,2,3,4,5,6}; The above array is sorted in increasing and non-decreasing order. Now, let’s add a few duplicates. int arr[] = {1,1,2,2,3,4,4}; The above array is not in an increasing order. But it is in non-decreasing order.

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

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

Quicksort in C++

// cat quicksort.cc #include <bits/stdc++.h> #include <algorithm> // std::swap using namespace std; int partition(int arr[], int low, int high); void qsort(int arr[], int start, int end) { int p; if (start < end) { p = partition(arr, start, end); qsort(arr, start, p – 1); qsort(arr, p + 1, end); } } int partition(int arr[], int…

Find a Fibonacci Number with Matrix Exponentiation

Core Concepts We can represent any number with a power of (2 or 3 or anything). Evidence? The binary system 🙂 So we can represent any number with log n bits and using 2 as the exponent. f(n) = f(n-1) + f(n-2) => f(n) = 1*f(n-1) + 1*f(n-2) [f(n)] = |1 1| * |f(n-1)| |f(n-2)|…

Another Solution: Longest Palindrome Substring

class Solution(object): def __init__(self): self.lookup = {“test”} def isPalindrome(self, s, i, k): j = i + k – 1 if s[i] == s[j]: key = self.createKey(i + 1, j – 1) if key in self.lookup: #self.lookup.remove(key) return True return False def createKey(self, i, j): #return “{}:{}”.format(i,j) #return (i, j) #key = bin(i) + bin(j) #return…

Longest Palindrome Substring in a String

DP based solution class Solution(object): def __init__(self): self.lookup = {} def isPalindrome(self, s, dp, i, k): j = i + k – 1 if s[i] == s[j] and dp[i + 1][j – 1]: return True return False def longestPalindrome(self, s): “”” :type s: str :rtype: str “”” size = len(s) if size < 2: return…