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…

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

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

Pitfall of C array

CODE int main() { int my_array[4] = {11,12,13,14}; int next = 15; printf("\nSurprise = %d", my_array[4]); } What should it print? Well, although illegal, the above code does legal things. The array "my_array" has four integers allocated on the stack. The next integer "next" is allocated adjacent to the stack memory. So the address of…

Unfolding 2-D array in C

Last weekend my friends and I had a discussion on 2-D array in C. Surprisingly it went long as everyone had some points and knowledge to share 🙂 Finally we could gather some important information and understood this pearl of C better. I'll clear this idea with C code snippets. // Declare an arrayint arr[2][3]=…

%d bloggers like this: