Given an array of numbers A, find out whether it contains a 1-3-2 pattern. An 1-3-2 pattern is a subsequence of three numbers, A[i], A[j] and A[k] such that i<j<k and A[i] < A[k] < A[j]. For clarity, let's call the 1-3-2 pattern the Bronze-Gold-Silver pattern. If A[j] is Gold, then we should consider the …

Read More

Problem Given an integer array A, in one step, remove all elements A[i] where A[i-1] > A[i]. Return the number of steps performed until A becomes a non-decreasing array. See examples at LeetCode 2289. Solution The naive approach executes steps one by one. Store integers in a Linked List. At each step, find all …

Read More

Problem In a connected network consisting of N nodes, each node is connected to either one or two neighbors, forming a line topology. The task is to develop a program that runs on each node, calculating the total number of nodes in the network. Each node is aware of its neighboring nodes and can exchange messages with …

Read More

Problem An event consists of multiple properties, each defined as a key-value pair, where the key is a string and the value is of a primitive type such as numbers or strings. Importantly, each event must include a mandatory 'Name' property. Given a list of events, the task is to count the number of events based on …

Read More

A function is monotonic if it preserves the order of its arguments, i.e., if $x \le y$, then $f(x) \le f(y) $. In this post, we look at a class of problems where the argument is an interval. By identifying monotonic functions, we can reduce number of intervals to enumerate by an order of magnitude, from $O(n^2)$ to …

Read More

Given an array of numbers $A$, for each number $A[i]$, find the largest subarray that contains $A[i]$ and $A[i]$ is the minimum of the subarray. For example, for $A=[2, 0, 3, 5, 1, 1, 0, 2 1]$, the largest subarray for $A[4]$ is $[3,5,1,1]$. Let's represent the subarray for $A[i]$ as the left boundary $l[i]$ and right …

Read More

Given two sorted arrays of integers, $A$ and $B$, find the $K$-th smallest integer from A and B in $O(\min(\log{N}, \log{M}))$ time. $N$ and $M$ are the size of $A$ and $B$ respectively. Without loss of generality, we can assume A and B are of the same length N. Because both A and B are sorted, we can merge A and B …

Read More