Problem Solving Fundamentals: From a Question to an Algorithm

Imagine a friend who runs a small online shop says, "Can you tell me which stretch of days we did well?" Is "well" above a certain amount, or above the average? Is a stretch any group of days, or consecutive days only? Should the answer be the longest stretch, the best one, or the most recent?

A problem statement is a request from a person who knows what they mean and is not telling you everything. Most beginners start coding straight away and solve the wrong problem very efficiently. This article teaches you to slow down for two minutes at the start so you do not lose two hours at the end.

• How to extract inputs, outputs, constraints and assumptions from a problem statement.
• How to use the input size to decide how fast your solution needs to be.
• How to pick examples that expose mistakes, and how to list edge cases.
• How to break a problem into steps and write pseudocode.
• How to write a brute-force solution, find its wasted work and improve it.

Before you write anything, answer these questions in your own words.

When you are in an interview, ask these questions out loud. Interviewers like it, because it is what a good colleague does. When you are practising alone, write the answers down, because writing forces precision.

Here is a problem we will use through this article. It is original, small and rich enough to show every step.

Longest good streak. A shop records its sales amount for each day, in order, in an array sales. A day is "good" if its sales are at least target. Return the length of the longest run of consecutive good days.

Let us run the questions on it.

• Input: an array of integers sales and an integer target.
• Output: one integer, the length of the longest run of consecutive good days.
• Constraints: none were given. We would ask. Suppose the answer is "up to 100,000 days".
• Assumptions: sales can be zero. Negative values are possible if returns are recorded. We treat each element on its own, nothing needs to be sorted.
• Unusual input: an empty array has no days, so the answer is 0. If no day is good, the answer is also 0.

Notice that we did not write code and we already know a great deal.

The size of the input tells you how much work your solution may do. A computer can do roughly tens or hundreds of millions of simple operations in a second. The exact number depends on the machine, the language and the platform, so treat the following as a rough guide and not as a law.

The next article, Time and Space Complexity Without the Confusion, explains the O(...) notation properly. For now, read "O(n^2)" as "the work grows with the square of the input size".

For our shop, n is up to 100,000, so a solution that compares every pair of days is too slow. We will keep that in mind.

Constraints on values matter too. If values can reach two billion and you add a few of them, an int may overflow. We will meet that in the next two articles.

Good examples are chosen to try to break your idea. For each problem, write:

• One normal example you can solve by eye.
• The smallest case. Empty input, a single element.
• An all-same case. Everything equal, everything good, everything bad.
• A boundary case. A value exactly equal to the threshold. A streak at the very start or the very end.
• A case where the answer is not at the start. This catches code that only looks at the beginning.

For the shop, with target = 7:

Write these before the code, and you have a test suite waiting.

Large problems feel impossible. Small steps do not. Ask: "If I were doing this by hand on a printed list, what would I do?"

By hand you would move your finger along the days. Each time you see a good day you add one to a running count. When you see a bad day, the streak is over, so you reset the count to zero. Whenever the running count beats the best streak so far, you remember it.

That description is already an algorithm. Writing it in a structured way is called pseudocode.

Pseudocode is a plain-English version of code. It has no strict syntax. Its purpose is to let you design the steps without fighting a compiler.

best = 0current = 0for each value in sales:    if value >= target:        current = current + 1        best = max(best, current)    else:        current = 0return best

A few rules for good pseudocode:

• Use short, precise verbs: set, add, compare, return, repeat.
• Name things the way you will name them in code.
• Keep indentation to show structure, as in the example.
• Do not hide hard steps behind vague words. "Process the array" is not a step.

A brute-force solution tries everything simple and obvious. It is usually slow but it is easy to get right. There are three reasons to write it first:

1. It gives you a correct answer to compare against.
2. It proves you understand the problem.
3. Its wasted work shows you where the speed-up is hiding.

For the shop, the brute force is: "Try every day as the starting day. From there, keep going while the days are good. Remember the longest."

best = 0for start from 0 to n - 1:    end = start    while end < n and sales[end] >= target:        end = end + 1    best = max(best, end - start)return best

Let us make both versions real Java and run them side by side.

// File: Main.javapublic class Main {    // Brute force: try every starting day and extend as far as the streak lasts.    static int longestStreakBrute(int[] sales, int target) {        int best = 0;        for (int start = 0; start < sales.length; start++) {            int end = start;            while (end < sales.length && sales[end] >= target) {                end++;            }            best = Math.max(best, end - start);        }        return best;    }    // One pass: keep the length of the streak that is running right now.    static int longestStreak(int[] sales, int target) {        int best = 0;        int current = 0;        for (int value : sales) {            if (value >= target) {                current++;                best = Math.max(best, current);            } else {                current = 0;            }        }        return best;    }    public static void main(String[] args) {        int[][] tests = {            {5, 8, 9, 3, 7, 7, 7, 2},            {1, 2, 3},            {10, 10, 10},            {},            {9},            {7},            {-3, -1, -2}        };        int target = 7;        for (int[] sales : tests) {            System.out.println(longestStreakBrute(sales, target) + " " + longestStreak(sales, target));        }    }}

3 30 03 30 01 11 10 0

Both columns match the "Longest good streak" column in our table. Having two independent solutions agree is a strong sign, and it is a technique you can reuse: write the slow obvious version and use it to check the fast clever version.

Trace the brute force on [5, 8, 9, 3, 7, 7, 7, 2] with target = 7.

Look at starts 1 and 2. When we started at day 1 we already walked over day 2 and learned that it begins a good run of length 1 that ends at the same place. Starting again at day 2 re-reads the same days. The same happens for starts 4, 5 and 6.

That is the wasted work: we keep re-walking days we have already seen. The improvement writes itself. Walk through the days once, and carry along what we learned: the length of the streak running right now.

Same input, target = 7:

Returns 3. Every day was looked at exactly once.

• Brute force. In the worst case, every day is good. Start 0 walks n days, start 1 walks n - 1, and so on, so the total is n + (n - 1) + ... + 1, which is n * (n + 1) / 2. We say the time is O(n^2) and the extra space is O(1). For n = 100,000 that is about five billion steps, which is too slow.
• One pass. The loop runs n times and each iteration does a constant amount of work. Time is O(n) and extra space is O(1), because we only keep best and current.

For this particular problem the brute force would barely pass a test with n = 5,000 and would fail one with n = 100,000. The constraints told us that in advance.

Our second example has more traps, which makes it a better workout for the edge-case habit.

Second largest. Given an array of integers, return the second largest distinct value. If there are fewer than two distinct values, there is no answer.

The word distinct is a decision. In [9, 9, 4], is the second largest 9 or 4? We chose distinct, so it is 4. If the problem statement does not say, you ask.

Brute force: sort a copy of the array, then walk backwards from the end until you find a value different from the largest.

Optimization: sorting does more work than we need, because we only care about the top two values. One pass can track the largest and the second largest seen so far.

Here is the trap: how do you represent "nothing seen yet"? If you start first and second at Integer.MIN_VALUE, the array [Integer.MIN_VALUE, 5] breaks, because the real minimum value looks like "nothing yet". We avoid this by tracking the two values in long variables and using Long.MIN_VALUE, which is smaller than any int.

// File: Main.javaimport java.util.Arrays;public class Main {    // Brute force: sort a copy, then look for the first value below the maximum.    static Integer secondLargestSorted(int[] numbers) {        int[] copy = Arrays.copyOf(numbers, numbers.length);        Arrays.sort(copy);        for (int i = copy.length - 2; i >= 0; i--) {            if (copy[i] != copy[copy.length - 1]) {                return copy[i];            }        }        return null; // fewer than two distinct values    }    // One pass: track the two largest distinct values seen so far.    static Integer secondLargest(int[] numbers) {        long first = Long.MIN_VALUE;  // no int is this small, so it safely means "nothing yet"        long second = Long.MIN_VALUE;        for (int value : numbers) {            if (value > first) {                second = first;                first = value;            } else if (value < first && value > second) {                second = value;            }        }        return second == Long.MIN_VALUE ? null : (int) second;    }    public static void main(String[] args) {        int[][] tests = {            {4, 9, 2, 9, 7},            {5, 5, 5},            {},            {3},            {Integer.MIN_VALUE, 5}        };        for (int[] test : tests) {            System.out.println(secondLargestSorted(test) + " " + secondLargest(test));        }    }}

7 7null nullnull nullnull null-2147483648 -2147483648

A method that returns Integer (the object version of int) can return null to say "there is no answer". We explain why in Java Essentials for DSA.

Walk through [4, 9, 2, 9, 7] in the one-pass version:

The answer is 7. The value < first check is what makes the second 9 get ignored, which is exactly the "distinct" part of the requirement.

Complexity: sorting version O(n log n) time and O(n) extra space for the copy. One-pass version O(n) time and O(1) extra space.

• Solving a slightly different problem. Re-read the statement after your first example. Did you assume sorted input, positive numbers or unique values?
• Treating "empty" as impossible. If it is allowed, handle it. If it is not, say so.
• Off-by-one errors. Decide whether your range is inclusive or exclusive. end - start is a length; end - start + 1 would be too long.
• Bad sentinels. Starting max at 0 fails for all-negative arrays. Starting it at Integer.MIN_VALUE is safer, but starting it at the first element is the safest when the array is not empty.
• Ignoring overflow. If values or sums can exceed about two billion, use long.
• Optimising before you have a correct baseline. A fast wrong answer is worth nothing.
• Forgetting to test the boundary of the condition. > versus >= is the most common single-character bug.

static int longestStreakBuggy(int[] sales, int target) {    int best = 0;    int current = 0;    for (int value : sales) {        if (value > target) {            current++;        }        best = Math.max(best, current);    }    return best;}

// File: Main.javapublic class Main {    static double average(int[] marks) {        if (marks.length == 0) {            throw new IllegalArgumentException("marks must not be empty");        }        long sum = 0;        for (int mark : marks) {            sum += mark;        }        return (double) sum / marks.length;    }    public static void main(String[] args) {        System.out.println(average(new int[] {75}));        System.out.println(average(new int[] {3, 4}));        System.out.println(average(new int[] {2_000_000_000, 2_000_000_000}));        int badSum = 2_000_000_000 + 2_000_000_000; // overflows int        System.out.println(badSum);    }}

75.03.52.0E9-294967296

// File: Main.javapublic class Main {    static long maxDifferenceBrute(int[] a) {        long best = (long) a[1] - a[0];        for (int i = 0; i < a.length; i++) {            for (int j = i + 1; j < a.length; j++) {                best = Math.max(best, (long) a[j] - a[i]);            }        }        return best;    }    static long maxDifference(int[] a) {        int minSoFar = a[0];        long best = (long) a[1] - a[0];        for (int j = 1; j < a.length; j++) {            best = Math.max(best, (long) a[j] - minSoFar);            minSoFar = Math.min(minSoFar, a[j]);        }        return best;    }    public static void main(String[] args) {        int[][] tests = {            {7, 2, 9, 4},            {9, 5, 3},            {1, 2},            {Integer.MAX_VALUE, Integer.MIN_VALUE}        };        for (int[] test : tests) {            System.out.println(maxDifferenceBrute(test) + " " + maxDifference(test));        }    }}

7 7-2 -21 1-4294967295 -4294967295

// File: Main.javapublic class Main {    static int longestStreakBuggy(int[] sales, int target) {        int best = 0;        int current = 0;        for (int value : sales) {            if (value > target) {                current++;            }            best = Math.max(best, current);        }        return best;    }    static int longestStreakFixed(int[] sales, int target) {        int best = 0;        int current = 0;        for (int value : sales) {            if (value >= target) {                current++;            } else {                current = 0;            }            best = Math.max(best, current);        }        return best;    }    public static void main(String[] args) {        System.out.println(longestStreakBuggy(new int[] {7, 7}, 7) + " " + longestStreakFixed(new int[] {7, 7}, 7));        System.out.println(longestStreakBuggy(new int[] {9, 3, 9}, 8) + " " + longestStreakFixed(new int[] {9, 3, 9}, 8));    }}

0 22 1

// File: Main.javapublic class Main {    static int countDistinctSorted(int[] sorted) {        if (sorted.length == 0) {            return 0;        }        int count = 1; // the first element is always a new value        for (int i = 1; i < sorted.length; i++) {            if (sorted[i] != sorted[i - 1]) {                count++;            }        }        return count;    }    public static void main(String[] args) {        System.out.println(countDistinctSorted(new int[] {1, 1, 2, 3, 3, 3}));        System.out.println(countDistinctSorted(new int[] {}));        System.out.println(countDistinctSorted(new int[] {7}));        System.out.println(countDistinctSorted(new int[] {2, 2, 2}));    }}

3011

• Next: Java Essentials for DSA gives you the language tools: types, overflow, arrays, strings and basic input.
• Then: Time and Space Complexity Without the Confusion turns "too slow" into a number.
• Looking ahead: you will see the "remember what you have already learned" idea again in Sliding Window and Prefix Sums.