Array Theory

Table of Contents

Cycle Sort

  • Decrease and conquer algorithm
  • Calculation of rank happens at most 2 times
  • The time complexity is $O(n^2). There is a special case where we need not calculate the rank and this makes the algorithm run in \(O(n)\). All the cycle sort problems belong to this category.
Problem Attempts Best Time Last Tried Difficulty Tags Status
https://leetcode.com/problems/subsets 4 3 min 14 seconds 02/17/2022 Medium LC78,recursion, IK, combination Good Job Suresh!
https://leetcode.com/problems/subsets-ii 4 13 min 47 seconds 02/17/2022 Medium LC90, recursion, combination Made one mistake in counting the duplicate values. Focus on edge case
https://www.interviewkickstart.com/problems/palindrome-partitioning 2 23 min 02/10/2022 Medium IK01,recursion, combination Needs lots of Practice
https://leetcode.com/problems/generate-parentheses 1 30 min 02/19/2022 Medium LC22, recursion, combination, backtracking Needs lots of Practice
https://leetcode.com/problems/two-sum 3 3 min 01/10/2022 Easy LC1,arrays, hashmap Needs Practice...because I made a syntax error
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted 3 4 min 13 seconds 02/20/2022 Medium LC167, arrays, two pointer Got it right without any mistakes in one shot
https://leetcode.com/problems/concatenation-of-array 3 2 min 01/10/2022 Easy LC1929, arrays Needs Practice
https://leetcode.com/problems/remove-duplicates-from-sorted-array 2 6 min 12/13/2021 Easy LC26, arrays, two pointer Transform and conquer. Data is shuffled in-place in the array.
https://leetcode.com/problems/contains-duplicate 1 5 min 02/17/2022 Easy LC217, arrays Made a silly error of storing index instead of value in the dicitionary. I got this right earlier.
https://leetcode.com/problems/contains-duplicate-ii 2 15 min 12/24/2021 Easy LC219, arrays Needs Practice
https://leetcode.com/problems/read-n-characters-given-read4 1 25 min 11/10/2021 Easy LC157, arrays Understand the question and build coding fluency
https://leetcode.com/problems/mergesort 3 5 min 02/22/2022 Medium IK02, arrays, divide and conquer, sort I had to look up the base case.
https://leetcode.com/problems/n-th-tribonacci-number 2 5 min 02/18/2022 Easy LC1137, DP Made 2 mistakes before getting it right..incorrect ordering of assignment and syntax error
https://leetcode.com/problems/climbing-stairs 3 2 min 01/17/2022 Easy LC70, DP Needs Practice
https://leetcode.com/problems/best-time-to-buy-and-sell-stock 1 12 min 01/16/2022 Easy LC121, arrays Find maximum difference for max profit and the second number should be greater than the first one
https://leetcode.com/problems/intersection-of-three-sorted-arrays 1 18 min 01/10/2022 Easy LC1213,arrays, sorting Needs Practice
https://leetcode.com/problems/fibonacci-number 1 18 min 12/06/2021 Easy LC509, IK, DP Needs Practice
https://leetcode.com/problems/min-cost-climbing-stairs 1 20 min 01/17/2022 Easy LC746, DP Needs Practice
https://leetcode.com/problems/find-all-duplicates-in-an-array 1 20 min 01/17/2022 Medium LC442, arrays, Sorting Since numbers repeat once or twice, apply transform and conquer approach
https://leetcode.com/problems/permutations 1 4 min 02/19/2022 Medium LC46, recursion, IK, permutation
https://leetcode.com/problems/letter-case-permutation 3 4 min 02/01/2022 Medium LC784, recursion, combination Needs Practice
https://leetcode.com/problems/letter-combinations-of-a-phone-number 3 4 min 02/01/2022 Medium LC17, recursion, combination Needs Practice
https://leetcode.com/problems/targetsumIK 1 10 min 12/09/2021 Medium IK03, recursion, combination Needs Practice
https://leetcode.com/problems/sort-colors 2 07 min 02/22/2022 Medium LC75,arrays, IK, sorting, three pointer Needs Practice. Understand the concept
https://leetcode.com/problems/merge-sorted-array 4 7 min 02/22/2022 Easy LC88, arrays, IK, Sorting, Two pointer Combine from the back
https://leetcode.com/problems/boats-to-save-people 3 2 min 11/10/2021 Medium LC881, arrays, Two pointer Needs Practice
https://leetcode.com/problems/combinations 2 5 min 02/17/2022 Medium LC77, recursion, combination 2 Coding errors. Require Practice
https://leetcode.com/problems/running-sum-of-1d-array 2 1 min 02/17/2022 Easy LC1480,arrays, one pointer Confident
https://leetcode.com/problems/binary-trees-level-order-traversal 2 2 min 31 seconds 02/28/2022 Medium LC102, trees, IK, bfs Needs Practice
https://leetcode.com/problems/binary-trees-level-order-traversal-ii 2 3 min 24 seconds 02/28/2022 Medium LC107, trees, IK, bfs One mistake on reversing final result array
https://leetcode.com/problems/binary-trees-right-side-view 1 5 min 36 seconds 02/23/2022 Medium LC199, trees, IK, bfs Needs Practice
https://leetcode.com/problems/binary-trees-zigzag-level-order-traversal 3 11 min 03 seconds 02/28/2022 Medium LC103, trees, IK, bfs Made one mistake in declaring right_to_left flag. It should be outside all loops
https://leetcode.com/problems/n-ary-trees-level-order-traversal 3 2 min 04 seconds 02/28/2022 Medium LC429, trees, IK, bfs No mistake
https://leetcode.com/problems/path-sum 1 15 min 02/23/2022 Easy LC112, trees, IK, dfs (top down) Needs Practice
https://leetcode.com/problems/path-sum-ii 2 11 Min 54 seconds 03/04/2022 Medium LC113, trees, IK, dfs (top down) IK error case requires returning [[-1]] and IK uses node.value and LC uses node.val. By habit I type node.val instead of paying attention to the question.
https://leetcode.com/problems/diameter-of-binary-trees 2 09 min 40 seconds 03/04/2022 Easy LC543, trees, IK, dfs (bottom up) Needs Practice. Made multiple logical and syntax errors
https://leetcode.com/problems/count-univalue-subtreess 1 15 min 02/25/2022 Medium LC250, trees, IK, dfs (bottom up) Needs Practice
https://leetcode.com/problems/convert-sorted-array-to-binary-search-trees 1 06 min 15 seconds 02/25/2022 Easy LC108,trees, IK, bst, dfs (construction) Needs Practice
https://leetcode.com/problems/construct-binary-trees-from-preorder-and-inorder-traversal 1 06 min 15 seconds 02/25/2022 Medium LC105,trees, IK, dfs (construction) Needs Practice
https://leetcode.com/problems/average-of-levels-in-binary-trees 1 04 min 10 seconds 02/28/2022 Easy LC637,trees, IK, bfs Got right first time
https://leetcode.com/problems/find-largest-value-in-each-trees-row 1 04 min 42 seconds 02/28/2022 Medium LC515,trees, IK, bfs Got right first time
https://leetcode.com/problems/minimum-depth-of-binary-trees 1 06 min 33 seconds 02/28/2022 Easy LC111,trees, IK, bfs Got right first time
https://leetcode.com/problems/maximum-depth-of-binary-trees 1 04 min 10 seconds 03/01/2022 Easy LC104,trees, IK, bfs Got right first time
https://leetcode.com/problems/maximum-level-sum-of-a-binary-trees 1 10 min 53 seconds 03/01/2022 Medium LC1161,trees, IK, bfs Needs practice
https://leetcode.com/problems/univalued-binary-trees 1 05 min 10 seconds 03/01/2022 Easy LC965,trees, IK, bfs Got right first time
https://leetcode.com/problems/validate-binary-search-trees 1 05 min 10 seconds 02/28/2022 Medium LC98,trees, IK, bfs Needs lots of practice. Think successor and predecessor
https://leetcode.com/problems/cousins-in-binary-tree 1 05 min 10 seconds 03/02/2022 Easy LC993,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/populating-next-right-pointers-in-each-node 1 05 min 10 seconds 03/02/2022 Medium LC116,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/add-one-row-to-tree 1 05 min 10 seconds 03/02/2022 Medium LC623,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/maximum-width-of-binary-tree 1 05 min 10 seconds 03/02/2022 Medium LC662,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/check-completeness-of-a-binary-tree 1 05 min 10 seconds 03/02/2022 Medium LC958,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/same-tree 1 05 min 10 seconds 03/02/2022 Easy LC100,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/symmetric-tree 1 05 min 10 seconds 03/02/2022 Easy LC101,trees, IK, bfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence 1 05 min 10 seconds 03/02/2022 Medium LC298,trees, IK, dfs Needs lots of practice.
https://leetcode.com/problems/path-sum-iii 1 05 min 10 seconds 03/02/2022 Medium LC437,trees, IK, dfs Needs lots of practice.
https://leetcode.com/problems/invert-binary-tree 1 05 min 10 seconds 03/02/2022 Easy LC226,trees, IK, dfs Needs lots of practice.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree 1 05 min 10 seconds 03/02/2022 Medium LC236,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/longest-univalue-path 1 05 min 10 seconds 03/02/2022 Medium LC687,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/find-bottom-left-tree-value 1 05 min 10 seconds 03/02/2022 Medium LC513,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-vertical-order-traversal 1 05 min 10 seconds 03/02/2022 Medium LC314,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree 1 05 min 10 seconds 03/02/2022 Hard LC987,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/boundary-of-binary-tree 1 05 min 10 seconds 03/02/2022 Medium LC545,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-upside-down 1 05 min 10 seconds 03/02/2022 Medium LC156,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/balanced-binary-tree 1 05 min 10 seconds 03/02/2022 Easy LC110,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/largest-bst-subtree 1 05 min 10 seconds 03/02/2022 Medium LC333,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-maximum-path-sum 1 05 min 10 seconds 03/02/2022 Hard LC124,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii 1 05 min 10 seconds 03/02/2022 Medium LC117,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/merge-two-binary-trees 1 05 min 10 seconds 03/02/2022 Easy LC617,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-tilt 1 05 min 10 seconds 03/02/2022 Easy LC563,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list 1 05 min 10 seconds 03/02/2022 Medium LC426,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/kth-smallest-element-in-a-bst 1 05 min 10 seconds 03/02/2022 Medium LC230,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/flatten-binary-tree-to-linked-list 1 05 min 10 seconds 03/02/2022 Medium LC114,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-preorder-traversal 1 05 min 10 seconds 03/02/2022 Easy LC144,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-inorder-traversal 1 05 min 10 seconds 03/02/2022 Easy LC94,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-tree-postorder-traversal 1 05 min 10 seconds 03/02/2022 Easy LC145,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/binary-search-tree-iterator 1 05 min 10 seconds 03/02/2022 Medium LC173,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal 1 05 min 10 seconds 03/02/2022 Medium LC106,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree 1 05 min 10 seconds 03/02/2022 Medium LC109,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal 1 05 min 10 seconds 03/02/2022 Medium LC1008,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/serialize-and-deserialize-binary-tree 1 05 min 10 seconds 03/02/2022 Hard LC297,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/serialize-and-deserialize-bst 1 05 min 10 seconds 03/02/2022 Medium LC449,trees, IK, bottom_up_dfs Needs lots of practice.
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph 1 05 min 10 seconds 03/07/2022 Medium LC323,graphs, IK, bfs, dfs Needs lots of practice.
https://leetcode.com/problems/graph-valid-tree 1 05 min 10 seconds 03/07/2022 Medium LC261,graphs, IK, bfs, dfs Needs lots of practice.
https://leetcode.com/problems/find-smallest-letter-greater-than-target 2 03 min 10 seconds 03/15/2022 Easy LC744,arrays, binary search Repeat
https://leetcode.com/problems/search-insert-position 2 03 min 10 seconds 03/15/2022 Easy LC35,arrays, binary search Done
https://leetcode.com/problems/first-bad-version 2 03 min 10 seconds 03/15/2022 Easy LC278, arrays, binary search Done 
def rank(x, nums):
 count = 0
 for i in range(len(nums)):
   if nums[i] < x:
     count += 1
 return count + 1

def cyclesort(nums):
  for i in range(len(nums)):
    d = rank(nums[i], nums) - 1
    while i != d:
      nums[i], nums[d] nums[d], nums[i]
      d = rank(nums[i], nums) - 1

Time Complexity: = \(O(n^2)\)

Space Complexity: = \(O(1)\)

  • We could have just overwritten the array instead of sorting if the index and values are same ? why bother sorting?

    • This is because we assume there could be transaction objects in the

    array and not primitive integers. Assume the array was holding transactions based on sale price to begin with and once the book keeping is done, we are sorting it by transaction id.

  • This is called cycle sort because each number may be initially in index that belongs to another number and we can find a cycle if we try to draw where actually the numbers should be and where they are initially placed.

  • Focus on the (number, original index) pair and we could use any sorting algorithm to sort it if we could use extra space to recor the frequency/index and we can make the sort stable.

  • Question about stability in cycle sort is acadmeic because usually we will be dealing with distinct numbers and stability does not really apply if there are no duplicates.

  • The time complexity is \(O(N)\) because there is no more comparison here as we are doing constant amount of work by looking at its index.

  • Can all elements occupy one cycle? Yes, the use case is rotation by 1.

  • Every swap defaltes the cycle by 1. A cycle of size n requires n -1 swaps to fully deflate all the cycle.

Sorting with Omkar_Part 2 Video Notes:

  • Search Engine Design:

    • Search engine uses a data structure called inverted index. Given a word, returns list of page numbers of sorted order.

    • Inverted index or search index, tells you given a word, a list of documents Ids which contain the word.

    • Given a list of doc ids, each line of each doc is parsed and added to dictionary as key and the value is a list which holds the doc.id

    • How do we find all doc ids that satisfy boolean queries? Say word1 and word2. This means we need to look at all the lists and find those doc ids that appear in all the lists?

      • To do this, we have to take intersection of the lists. (This is not implemented as lists but dynamic arrays and called Posting lists)
      • The posting lists do not have any duplicates within the same array.

References:

Interview Kickstart:

arrays cycle_sort
Previous
Next

Last updated on Apr 6, 2023

Edit this page