Assume, Then Disprove (Flag and Early Exit)

Assume, Then Disprove means you start by believing the answer is "yes" (a flag set to true), then scan for a single counter-example that proves it wrong. The moment you find one, you flip the flag and stop, because one failure is enough to settle the question. Interviewers like it because it tests whether you can turn "for all" statements into a simple loop and whether you know when to quit early.

When to use it

  • The question asks 'is it always true that...', 'are all elements...', or 'does every ... satisfy ...'
  • You are checking a property such as sorted, palindrome, valid, unique, or balanced, and the answer is a boolean
  • A single bad item is enough to make the whole answer 'no'
  • Words like 'any', 'all', 'never', or 'every' appear in the problem
  • Checking everything would be wasteful, since the first violation already gives the answer

See it work

  1. Goal: is the array [2, 4, 7, 5, 9] sorted in ascending order? We assume yes, so we start with ok = true. Then we compare each neighbouring pair, looking for one pair that breaks the rule. [2, 4, 7, 5, 9]
  2. Compare index 0 and 1: 2 <= 4. No problem, so no counter-example yet. The flag stays true. [2, 4, 7, 5, 9]
  3. Compare index 1 and 2: 4 <= 7. Still fine. The flag stays true. [2, 4, 7, 5, 9]
  4. Compare index 2 and 3: 7 <= 5 is false. This is our counter-example: a pair that is out of order. [2, 4, 7, 5, 9]
  5. Set ok = false and return immediately. We never look at the 9 at the end, because nothing there could undo the failure. That skipped work is the early exit. [2, 4, 7, 5, 9]
  6. If the array had been [2, 4, 5, 7, 9], every pair would pass, the loop would end with no counter-example, and the flag would still be true. We only say yes after checking everything. [2, 4, 5, 7, 9]

Code template

Python

def holds_for_all(items):
    ok = True                      # assume the answer is yes
    for i in range(len(items)):
        if violates(items, i):     # look for ONE counter-example
            ok = False             # flip the flag
            break                  # early exit: no need to continue
    return ok

# Often you can skip the flag and return directly:
def holds_for_all_short(items):
    for i in range(len(items)):
        if violates(items, i):
            return False           # disproved
    return True                    # no counter-example exists

C

#include <stdbool.h>

bool holds_for_all(const int *items, int n) {
    bool ok = true;                    /* assume the answer is yes */
    for (int i = 0; i < n; i++) {
        if (violates(items, i)) {      /* look for ONE counter-example */
            ok = false;                /* flip the flag */
            break;                     /* early exit */
        }
    }
    return ok;
}

/* Direct-return version: */
bool holds_for_all_short(const int *items, int n) {
    for (int i = 0; i < n; i++) {
        if (violates(items, i)) return false;  /* disproved */
    }
    return true;                       /* no counter-example exists */
}

Java

static boolean holdsForAll(int[] items) {
    boolean ok = true;                 // assume the answer is yes
    for (int i = 0; i < items.length; i++) {
        if (violates(items, i)) {      // look for ONE counter-example
            ok = false;                // flip the flag
            break;                     // early exit
        }
    }
    return ok;
}

// Direct-return version:
static boolean holdsForAllShort(int[] items) {
    for (int i = 0; i < items.length; i++) {
        if (violates(items, i)) return false;  // disproved
    }
    return true;                       // no counter-example exists
}

Complexity: Time is O(n) in the worst case (no counter-example, so you scan everything) but often much less thanks to the early exit; space is O(1) since you only keep one flag.

Programs that use it

Interview problems that use it

  • Is the array sorted?: Assume it is sorted, compare each neighbouring pair, and return false at the first pair where the left value is bigger than the right.
  • Valid palindrome check: Assume the string reads the same both ways, compare characters from both ends moving inward, and return false at the first mismatch.
  • Contains duplicates (all elements unique?): Assume all values are unique, keep a set of seen values, and return false the moment you see a value already in the set.
  • Valid parentheses: Assume the brackets are balanced, push openers on a stack, and return false as soon as a closer does not match the top or the stack is empty.
  • Can you reach the last index of a jump array?: Track the farthest reachable position; if you arrive at an index beyond it, you have a counter-example to 'reachable' and can return false right away.
  • Is a number prime?: Assume it is prime, try divisors from 2 up to the square root, and return false at the first divisor that divides it evenly.

Common mistakes

  • Returning true too early: finding one item that passes the check proves nothing. You may only answer 'yes' after the whole loop finishes with no counter-example.
  • Forgetting to stop after flipping the flag. If you set ok = false but keep looping, you waste time and may accidentally overwrite the flag back to true.
  • Skipping edge cases: an empty array or a single element has no pair to violate the rule, so the correct answer is usually true. Make sure your loop bounds (for example i < n - 1 for pair checks) do not go out of range.

Frequently asked questions

Why start with the flag set to true instead of false?

Because the question is a 'for all' claim, and a claim about everything is true until something breaks it. Starting at true means the only thing you have to detect is a failure, which is exactly what the loop searches for. An empty input then correctly returns true.

Do I really need a flag variable, or can I just return false?

Returning false directly inside the loop and returning true after it is usually cleaner and does the same job. Use a separate flag when you must do more work after the loop, such as cleanup, logging, or combining several checks.

How is this different from just looping through everything?

A full pass always costs O(n). With early exit, the loop ends at the first counter-example, so bad inputs are rejected quickly. The worst case is the same, but the average case is often much faster, and the code states your intent clearly: find one failure and stop.

← All interview patterns

Try AI Flowchart free →