New answers tagged

0 votes

Why do the pointers in Two-pointer algorithm move only towards each other?

Consider a situation where Pointer 1 is equal to $i$ and Pointer 2 is equal to $j$, and $A[i] + A[j] > K$. The last time Pointer 1 was incremented, Pointer 2 was in a position $j' \geqslant j$. ...
user avatar
  • 7,127
0 votes

Find a subsequence with fastest time for specific distance

Here is an $O(n)$ two-finger algorithm for the problem in Python: ...
user avatar
0 votes

Maximum subarray sum of given length range

This answer explains an $O(n)$-time algorithm. Basic Ideas The ideas are classic. "Sum of the elements in subarray" -- prefix sums. "Length between a...
user avatar
  • 33k
5 votes

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

Lemma: For any $i<j$, if $A[i]<A[j]$, there are certainly two neighboring elements in $A[i..j]$ such that $A[k]<A[k+1]$. Otherwise, the subarray would be non-increasing and this contradicts $...
user avatar
  • 3,318
3 votes
Accepted

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

You are almost there. "If yes then an index $i$ that satisfies $a[i]<a[i+1]$, will surely appear on the right side"; so continue searching on the right side. If no, continue searching on ...
user avatar
  • 33k
1 vote
Accepted

Maximum subarray sum of given length range

By augmenting an AVL tree you can implement a data structure that maintains a multi-set $S$ under the following $O(\log |S|)$-time operations: Add($S, x$): Add number $x$ to $S$. Offset($S, x$): ...
user avatar
  • 22.7k
1 vote

Maximum difference between maximum and minimum frequency in a subarray

We can provide an $O(n)$ algorithm for such a problem For every pair of characters $(c_1,c_2)$, we take the input string, ignore all other characters, replace $c_1$ by $1$, replace $c_2$ by $-1$ and ...
user avatar
  • 609
2 votes
Accepted

Maximum difference between maximum and minimum frequency in a subarray

Your problem can be solved in linear time in the length of the input string. Let $s=s_1s_2s_3\ldots$ be your input string. For $0<i\le j \le |s|$, let $n(i,j,c)$ be the number of occurrences of $c$ ...
user avatar
  • 22.7k

Top 50 recent answers are included