Counting and two pointers
Read · 1 of 3
Two one-pass tricks
Counting array: when values are small (say 0 to 1000), int count[1001] = {0}; and count[x]++ for each x tells you how often everything appears, in one pass.
Two pointers: in a sorted array, to find two numbers adding to a target, start one pointer at each end. Sum too small? Move the left one right. Too big? Move the right one left. Each step rules out a whole row of pairs, so it's n steps instead of n².
Read this lesson as text
Answer questions in one pass with a counting array, or by walking from both ends of a sorted array.
Two one-pass tricks
Counting array: when values are small (say 0 to 1000), int count[1001] = {0}; and count[x]++ for each x tells you how often everything appears, in one pass.
Two pointers: in a sorted array, to find two numbers adding to a target, start one pointer at each end. Sum too small? Move the left one right. Too big? Move the right one left. Each step rules out a whole row of pairs, so it's n steps instead of n².
Exercise: Most frequent
Read n (1 to 100000) and n numbers between 0 and 1000. Print the value that appears most often and how many times; on a tie, the smaller value.
Exercise: Pair with a target sum
Read n (2 to 100000), n numbers in increasing order, and a target. Print Yes if two different positions add up to the target, else No. Use two pointers.