Count Good Triplets in an Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from sortedcontainers import SortedList

class Solution:
    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        # Index of a (from nums1) in nums2.
        position = [0] * len(nums1)
        for i, b in enumerate(nums2):
            position[b] = i

        # Build pre_nums1[i]: number of elements on nums1[i]'s left in both nums1 and nums2.
        # position_in_nums2: sorted indexes (in nums2) of all the visited elements in nums1.
        position_in_nums2, pre_nums1 = SortedList([position[nums1[0]]]), [0]
        for a in nums1[1:]:
            position_in_nums2.add(position[a])
            pre_nums1.append(position_in_nums2.bisect_left(position[a]))

        # Build suf_nums1[i]: number of elements on nums1[i]'s right in both nums1 and nums2.
        position_in_nums2, suf_nums1 = SortedList([position[nums1[-1]]]), [0]
        for a in reversed(nums1[:len(nums1)-1]):
            i = position_in_nums2.bisect(position[a])
            suf_nums1.append(len(position_in_nums2) - i)
            position_in_nums2.add(position[a])
        suf_nums1.reverse()

        # Sum up all unique triplets centered on nums1[i].
        answer = 0
        for x, y in zip(pre_nums1, suf_nums1):
            answer += x * y
        return answer

Identifying Problem Isomorphism

“Count Good Triplets in an Array” can be approximately mapped to “3Sum Smaller”.

Reasoning:

Both problems require us to find triplets in an array that satisfy certain conditions.

In “Count Good Triplets in an Array”, you are given an array of integers and you have to count the number of good triplets. A triplet (arr[i], arr[j], arr[k]) is considered good if the conditions are met according to the problem statement.

In “3Sum Smaller”, given an array of n integers nums and a target, you need to find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

There is a difference between these two problems. While “Count Good Triplets in an Array” involves absolute differences between pairs in the triplet, “3Sum Smaller” involves the sum of elements in the triplet.

“3Sum Smaller” is more complex due to the need for sorting the array and then using a two-pointer technique to find the triplets, while in “Count Good Triplets in an Array” a simpler brute force approach can be used to find all possible triplets and then check the conditions.

Clarification Questions

What are the clarification questions we can ask about this problem?

10 Prerequisite LeetCode Problems

“Count Good Triplets in an Array” is an array-based problem that involves finding certain ordered triplets in two arrays. Here are 10 problems to prepare:

  1. 167. Two Sum II - Input array is sorted: This problem practices finding pairs in an array with a certain property.

  2. 283. Move Zeroes: This problem involves modifying an array in place, a skill that could be useful.

  3. 88. Merge Sorted Array: This problem involves merging two arrays, a concept which might help you conceptualize working with two arrays simultaneously.

  4. 15. 3Sum: This problem is about finding triplets in a single array that sum to zero.

  5. 75. Sort Colors: This problem requires sorting an array with a specific strategy, and it could help in understanding array manipulations.

  6. 448. Find All Numbers Disappeared in an Array: This problem helps in understanding properties of array indices and elements.

  7. 442. Find All Duplicates in an Array: This problem is about finding certain elements in an array, which could help with understanding how to navigate and find elements in an array.

  8. 26. Remove Duplicates from Sorted Array: This problem requires an understanding of how to handle duplicates in an array.

  9. 11. Container With Most Water: This problem requires an understanding of how the arrangement of elements in an array can affect the problem outcome.

  10. 905. Sort Array By Parity: This problem is about rearranging elements in an array based on their properties, which might be a useful concept for this problem.

These cover how to manipulate and traverse arrays, needed for solving the “Count Good Triplets in an Array” problem.

Problem Classification

The problem falls into the domain of Array Manipulation and Combinatorial Search. The main task involves finding combinations of elements in two arrays that satisfy specific conditions.

‘What’ Components

  1. Input: Two 0-indexed arrays nums1 and nums2, both of length n, which are permutations of [0, 1, ..., n - 1].
  2. Target: To find the total number of “good triplets.”
  3. Constraints:
    • n == nums1.length == nums2.length
    • 3 <= n <= 105
    • 0 <= nums1[i], nums2[i] <= n - 1
    • Both arrays are permutations of [0, 1, ..., n - 1].
  4. Good Triplet: A triplet (x, y, z) that appears in increasing order in both arrays nums1 and nums2.
  • Search Problem: You need to search through all possible triplets to find the ones that meet the conditions.
  • Combination-based: The problem involves combinations of elements (x, y, z).
  • Order Sensitive: The position matters as the order needs to be maintained.
  • Counting Problem: The final output is a count of valid combinations, not the combinations themselves.

The problem fundamentally involves searching and combinatorics, requiring you to count specific sets of elements based on given conditions.

Distilling the Problem to Its Core Elements

1. Fundamental Concept

The problem is rooted in “Combinatorial Enumeration” under specific constraints. We are looking for all the triplets that meet a set of ordering criteria in two arrays.

2. Simplest Description

You have two lists of numbers. You want to find sets of three numbers that follow the same increasing order in both lists.

3. Core Problem

The core problem is to find the number of unique sets of three numbers (x, y, z) that appear in increasing order in both given lists.

4. Key Components

  • Two arrays nums1 and nums2, both containing unique integers.
  • A count of “good triplets”, where a good triplet means (x, y, z) that are in increasing order in both arrays.

5. Minimal Set of Operations

  1. Iterate through all combinations of (x, y, z) from the arrays.
  2. Check if each combination meets the conditions for being a “good triplet”.
  3. Keep a counter to record the number of “good triplets”.
  4. Return the counter as the final answer.

By performing these operations, we can solve the problem efficiently.

Visual Model of the Problem

Visualizing this problem can be done using a 2D grid or matrix. Each row could represent an array (nums1 or nums2), and the columns could represent the index positions in the arrays. Place the values of the arrays in the grid cells.

  1. Row 1 for nums1: Place the elements of nums1 in the first row.
  2. Row 2 for nums2: Place the elements of nums2 in the second row.

After filling the grid, use arrows to connect elements that make good triplets. Start with an element x in nums1, find y and z such that they are greater than x and form a good triplet. Do the same for nums2. If both nums1 and nums2 contain the same good triplet, highlight it.

Here’s a simplistic example for better understanding:

Example:

  • nums1 = [2,0,1,3]
  • nums2 = [0,1,2,3]
Index0123
nums12013
nums20123
  • Good triplet in both: (0, 1, 3)

Visualizing this way helps in quickly identifying the constraints and makes it easier to think about the conditions that a triplet has to meet to be considered “good”.

Problem Restatement

You have two arrays, nums1 and nums2, each with n elements. These arrays contain all the numbers from 0 to n-1 but in different orders. Your task is to find sets of three numbers (triplets) that appear in ascending order in both arrays by their positions. These sets are called “good triplets.”

Requirements:

  1. Each triplet must consist of distinct numbers from 0 to n-1.
  2. The numbers in each triplet should appear in increasing order in both nums1 and nums2 based on their positions in the arrays.

Constraints:

  1. Both arrays have the same length n, where 3 <= n <= 105.
  2. Each number from 0 to n-1 appears exactly once in each array.

The goal is to count and return the total number of such good triplets.

Abstract Representation of the Problem

In the most abstract terms, you have two ordered sets, A and B, each containing unique elements from a finite set S. The objective is to count the number of unique ordered subsets of size 3 from S that maintain their ordering in both A and B.

Key Elements:

  1. Two ordered sets A and B, both containing unique elements from S.
  2. An ordered subset of size 3 from S.

Constraints:

  1. Sets A and B are of the same finite size n.
  2. All elements in A and B are unique and belong to S.

Objective:

Count the number of unique ordered subsets of size 3 that are in ascending order in both A and B.

Terminology

Here are some terms that are crucial to understanding this problem:

  1. Permutation: An arrangement of elements in a specific order. Both nums1 and nums2 are permutations of the same set [0, 1, ..., n-1].

  2. Subset: A set of elements taken from a larger set without changing the order of the elements. In this problem, we’re focusing on subsets of size 3.

  3. Ordering: The arrangement of elements in a particular sequence. In this problem, we need the subsets to be in increasing order in both arrays.

  4. Index: The position of an element within an array. pos1x, pos1y, and pos1z are indices of elements x, y, and z in nums1.

  5. Constraint: Conditions that must be satisfied for a solution to be valid. Here, constraints include the length of arrays and the range of array elements.

These terms and concepts play vital roles in understanding the problem, defining its boundaries, and finding a solution.

Problem Simplification and Explanation

The problem asks you to find “good triplets” in two arrays. A good triplet is a set of three different numbers that appear in ascending order in both arrays.

Key Concepts:

  1. Arrays: Think of these as two different lists of names written by two people. Both have the same names but listed in different orders.

  2. Triplets: These are like picking three names from each list to form a group of friends.

  3. Good Triplets: These are the groups where the names appear in the same increasing alphabetical order on both lists.

  4. Ordering: This refers to the alphabetical order (or numerical in the problem) of the names in the list.

  5. Index: This is like the line number where the name appears on the list.

Metaphor:

Imagine two teachers have the same set of students but line them up differently after a game. You are tasked to form a team of three students, such that if Teacher 1 has them standing as Tom, Jerry, and Spike, Teacher 2 should also have them in the same order, even if not adjacent. These would be “good triplets” of teams.

Interactions:

  • You have to scan through both lists (arrays) to find these good teams (good triplets).
  • The position (index) of students (numbers) matters.
  • The sequence should be the same in both line-ups to be a “good triplet.”

By breaking it down like this, we see that we’re essentially looking for ordered sequences that appear in both lists.

Constraints

Here are some characteristics to consider for an efficient solution:

  1. Permutations: Both arrays are permutations of each other. This limits the range of possible values, simplifying the search for triplets.

  2. Bounded Range: All array elements are between 0 and ( n - 1 ). This bounded range might allow for more efficient sorting or searching algorithms.

  3. Array Length: The length of the arrays can go up to ( 10^5 ), which means an (O(n^2)) or (O(n^3)) solution would likely be too slow. Aiming for a linear or logarithmic solution would be beneficial.

  4. Same Length: Both arrays are of the same length ( n ), meaning we don’t need to handle mismatched sizes.

  5. Distinct Elements: All elements are distinct, so you don’t need to handle duplicates, which simplifies the search for triplets.

By recognizing these characteristics, you can tailor your algorithm to be more efficient, keeping in mind the array lengths and bounds to find a fast solution.

Analyzing the constraints gives us the following insights:

  1. Optimization Needed: The upper limit of ( n = 10^5 ) suggests that brute-force solutions with time complexities like (O(n^2)) or (O(n^3)) are not feasible. Aim for a linear or log-linear time complexity.

  2. Distinct and Bounded Elements: The fact that all elements are distinct and between 0 to ( n-1 ) allows us to potentially use data structures like hash tables or bit vectors for quick lookups and eliminate the need to deal with duplicates.

  3. Uniform Array Lengths: Since both arrays are of the same length, it simplifies our loops and conditional statements. We don’t have to worry about one array ending before the other.

  4. Permutation Nature: Both arrays are permutations of [0, 1, …, ( n - 1 )]. This can be exploited to quickly determine positions or rank of elements in either array, potentially facilitating faster comparisons or sorts.

  5. Triplet Requirement: The requirement of the elements to be in increasing order in both arrays for a “good triplet” suggests that a single scan won’t be sufficient; however, pre-processing might make this condition quicker to check.

The key takeaway is that we should aim for an efficient algorithm, likely involving some form of sorting or pre-processing, coupled with quick lookup data structures to meet the problem’s constraints effectively.

Case Analysis

Let’s look at some different types of test cases that will help in covering a broader input space.

1. Minimal Case

Input: nums1 = [0,1,2], nums2 = [0,1,2]
Output: 1
Reasoning: Here, the array length is the minimum allowed by the constraints (( n=3 )). Only one good triplet exists: (0,1,2). This case tests the lower bound of the input space.

2. Reverse Order Case

Input: nums1 = [2,1,0], nums2 = [0,2,1]
Output: 0
Reasoning: All the elements are in descending order in nums1, making it impossible to form a good triplet. This highlights the importance of order.

3. Partial Overlap Case

Input: nums1 = [0,1,2], nums2 = [1,0,2]
Output: 0
Reasoning: While both arrays contain the same elements, their orders aren’t compatible to form a good triplet. This emphasizes that order in both arrays matters.

4. Multiple Good Triplets Case

Input: nums1 = [0,3,1,2], nums2 = [0,1,3,2]
Output: 2
Reasoning: Two good triplets exist: (0,1,2) and (0,3,2). This demonstrates that multiple good triplets can exist in one set of arrays.

5. No Overlap Case

Input: nums1 = [0,1,2], nums2 = [2,1,0]
Output: 0
Reasoning: In this case, nums2 is the reverse of nums1, which means it’s impossible to form any good triplet.

6. One Array Sorted, One Array Random

Input: nums1 = [0,1,2,3], nums2 = [3,0,2,1]
Output: 0
Reasoning: nums1 is sorted, but the random nature of nums2 makes it impossible to form a good triplet. This case emphasizes that both arrays need to have elements in increasing positions to form a good triplet.

These test cases are carefully crafted to highlight the nuances of the problem, emphasize the constraints, and identify potential pitfalls. By solving for these, you can be more confident that your final solution is robust and well-rounded.

What are the key insights from analyzing the different cases?

Identification of Applicable Theoretical Concepts

Can you identify any mathematical or algorithmic concepts or properties that can be applied to simplify the problem or make it more manageable? Think about the nature of the operations or manipulations required by the problem statement. Are there existing theories, metrics, or methodologies in mathematics, computer science, or related fields that can be applied to calculate, measure, or perform these operations more effectively or efficiently?

Problem Breakdown and Solution Methodology

Given the problem statement, can you explain in detail how you would approach solving it? Please break down the process into smaller steps, illustrating how each step contributes to the overall solution. If applicable, consider using metaphors, analogies, or visual representations to make your explanation more intuitive. After explaining the process, can you also discuss how specific operations or changes in the problem’s parameters would affect the solution? Lastly, demonstrate the workings of your approach using one or more example cases.

Inference of Problem-Solving Approach from the Problem Statement

How did you infer from the problem statement that this problem can be solved using ?

Stepwise Refinement

1. Higher Level Steps

  1. Initial Understanding: Understand the properties that define a ‘good triplet’ in both arrays.
  2. Data Preparation: Create helper data structures to store the indices of the numbers in both arrays.
  3. Triplets Identification: Iterate through all possible triplets in nums1 and cross-verify them in nums2 using the helper data structures.
  4. Counting: Keep track of the number of ‘good triplets’ found.

2. Granular Steps

  1. Initialize a Counter: Declare a variable count to zero; it will store the number of good triplets.
  2. Create Position Dictionaries: Create dictionaries pos1 and pos2 for nums1 and nums2, where the key-value pairs are number-index.
  3. Iterate Through Triplets in nums1:
    1. Use three nested loops to go through each possible triplet (x, y, z) in nums1.
    2. Check if pos1[x] < pos1[y] < pos1[z]. If not, continue to the next iteration.
    3. Check if pos2[x] < pos2[y] < pos2[z]. If so, increment the counter.
  4. Return Counter: Once all loops are complete, return count.

3. Independent Parts

  1. Data Preparation: The creation of dictionaries pos1 and pos2 can be done independently of each other. They can even be created in parallel.
  2. Triplet Identification and Counting: These steps are interdependent and have to be performed sequentially.

4. Repeatable Patterns

  1. Index Mapping: Creating a dictionary to map numbers to their indices is a repeatable pattern, often used for quick look-up.
  2. Nested Iteration for Combinations: Using nested loops to go through all possible combinations is a common technique in combinatorial problems.
  3. Counter Initialization and Increment: This is a basic pattern where you initialize a counter and increment it when certain conditions meet.

By breaking down the problem this way, you can tackle each piece independently and understand the roles they play in the overall solution.

Solution Approach and Analysis

Approach to Solving the Problem

Step 1: Create Maps of Positions

  • What: Create two dictionaries to map each number in nums1 and nums2 to its position in the respective array.
  • Why: This enables quick look-up when we validate triplets.

Step 2: Initialize a Counter

  • What: Initialize a variable, say goodTriplets, to zero.
  • Why: To keep track of the total number of ‘good triplets’.

Step 3: Find Potential Triplets in nums1

  • What: Use three nested loops to identify all distinct triplets (x, y, z) from nums1.
  • Why: We have to check all combinations to find good triplets.

Step 4: Validate Each Triplet

  • What: For each triplet (x, y, z), validate if they are in increasing order in both arrays by using the dictionaries created.
  • Why: This is the core logic to identify a ‘good triplet’.

Step 5: Increment the Counter

  • What: If the triplet is good, increment goodTriplets by 1.
  • Why: To tally the number of good triplets found.

Step 6: Return the Counter

  • What: Once all possible triplets have been evaluated, return goodTriplets.
  • Why: This gives the total number of good triplets.

Metaphor

Imagine you have two books (nums1 and nums2) and you’re looking for the same three-word sentence (x, y, z) in both. You index every word’s page number (Step 1). Then, you go through one book and make a list of all three-word sentences (Step 3). You verify each sentence’s words are in the same order in the other book (Step 4). Each match counts as a good sentence (Step 5). In the end, you tally the number of good sentences (Step 6).

Operations or Changes in Problem Parameters

  • Increasing n: The bigger the size of the arrays, the more triplets there are to check. Computational time will increase substantially.
  • Constraints on Number Range: No impact, as it does not affect the triplet’s goodness.

Example Case: nums1 = [2,0,1,3], nums2 = [0,1,2,3]

  1. Step 1: pos1 = {2: 0, 0: 1, 1: 2, 3: 3}, pos2 = {0: 0, 1: 1, 2: 2, 3: 3}
  2. Step 2: goodTriplets = 0
  3. Step 3: One possible triplet is (2, 0, 1).
  4. Step 4: For (2, 0, 1), pos1 gives positions [0, 1, 2] and pos2 gives [2, 0, 1]. It’s not in increasing order in both, so skip.
  5. Step 5: No increment.
  6. Step 6: After all triplets are checked, we find that only (0, 1, 3) is a good triplet. Hence, goodTriplets = 1.

This approach can efficiently solve the problem while making sure that all constraints and edge cases are covered.

Thought Process

TLE shitgpt.

From Brute Force to Optimal Solution

Brute-Force Solution

In the most straightforward brute-force approach, you loop through all the triplets in nums1 and then check if they’re also a good triplet in nums2.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def countGoodTriplets(nums1, nums2):
    count = 0
    n = len(nums1)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                x, y, z = nums1[i], nums1[j], nums1[k]
                if nums1.index(x) < nums1.index(y) < nums1.index(z) and nums2.index(x) < nums2.index(y) < nums2.index(z):
                    count += 1
    return count

Inefficiencies

  1. Time Complexity: (O(n^3 \times 3)) = (O(n^3)) (Nested loops for each triplet, and for each triplet, finding index three times in both arrays)
  2. Space Complexity: (O(1)) (Only using constant extra space)

Optimized Solution

Step 1: Store Positions in a Dictionary

Storing the positions of each number in both nums1 and nums2 in dictionaries. This will allow for quick look-up.

Step 2: Use Stored Positions to Validate Triplets

Use the stored positions to validate the conditions for a ‘good triplet’ instead of searching for indices again.

Optimized Code

TLE

Analysis

  1. Time Complexity: (O(n^3)) (Still three nested loops, but each triplet check is now (O(1)))
  2. Space Complexity: (O(n)) (Storing positions of each number)

Impact

The optimized solution is significantly faster for each individual triplet check. This doesn’t reduce the polynomial degree of the time complexity, but it makes the function faster by a constant factor.

Code Explanation and Design Decisions

Refer working solution in LC.

Coding Constructs

  1. What are the high-level problem-solving strategies or techniques being used by this code?

  2. If you had to explain the purpose of this code to a non-programmer, what would you say?

  3. Can you identify the logical elements or constructs used in this code, independent of any programming language?

  4. Could you describe the algorithmic approach used by this code in plain English?

  5. What are the key steps or operations this code is performing on the input data, and why?

  6. Can you identify the algorithmic patterns or strategies used by this code, irrespective of the specific programming language syntax?

Language Agnostic Coding Drills

Your mission is to deconstruct this code into the smallest possible learning units, each corresponding to a separate coding concept. Consider these concepts as unique coding drills that can be individually implemented and later assembled into the final solution.

  1. Dissect the code and identify each distinct concept it contains. Remember, this process should be language-agnostic and generally applicable to most modern programming languages.

  2. Once you’ve identified these coding concepts or drills, list them out in order of increasing difficulty. Provide a brief description of each concept and why it is classified at its particular difficulty level.

  3. Next, describe the problem-solving approach that would lead from the problem statement to the final solution. Think about how each of these coding drills contributes to the overall solution. Elucidate the step-by-step process involved in using these drills to solve the problem. Please refrain from writing any actual code; we’re focusing on understanding the process and strategy.

Targeted Drills in Python

Now that you’ve identified and ordered the coding concepts from a complex software code in the previous exercise, let’s focus on creating Python-based coding drills for each of those concepts.

  1. Begin by writing a separate piece of Python code that encapsulates each identified concept. These individual drills should illustrate how to implement each concept in Python. Please ensure that these are suitable even for those with a basic understanding of Python.

  2. In addition to the general concepts, identify and write coding drills for any problem-specific concepts that might be needed to create a solution. Describe why these drills are essential for our problem.

  3. Once all drills have been coded, describe how these pieces can be integrated together in the right order to solve the initial problem. Each drill should contribute to building up to the final solution.

Remember, the goal is to not only to write these drills but also to ensure that they can be cohesively assembled into one comprehensive solution.

Q&A

Similar Problems

  1. Three Sum: Requires looping through triplets and has a similar combinatorial nature.
  2. Valid Triangle Number: Involves iterating over triplets and checking conditions.
  3. Increasing Triple Subsequence: Requires finding a sequence of three numbers that meet specific criteria.
  4. Combination Sum III: You’re also generating triplets, albeit with a different validation condition.
  5. 3Sum Smaller: Asks you to find triplets that meet certain conditions.
  6. Subsets II: Involves combinatorial logic, much like generating triplets.
  7. 4Sum: An extension of 3Sum, and requires similar looping and condition-checking strategies.
  8. Palindrome Pairs: Although string-based, it involves pairing and validating, similar to checking triplets.
  9. Permutation Sequence: As the original problem deals with permutations, solving this will give insights into handling permutations efficiently.
  10. Find All Duplicates in an Array: Provides experience in using data structures like dictionaries to store frequencies or positions for quick look-up, which is useful in our original problem for optimization.

Each of these problems involves a similar thought process: break the problem down into smaller parts, consider the combinatorial aspects, and optimize.

My Notes

Count Good Triplets excerpt: This covers preventing off by one errors and reducing the domains of the variables. tags: reducing-the-domains-of-the-variables off-by-one-error out-of-bounds-error

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length |arr[i] - arr[j]| <= a |arr[j] - arr[k]| <= b |arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

Constraints

  • 3 <= arr.length <= 100
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# @param {Integer[]} arr
# @param {Integer} a
# @param {Integer} b
# @param {Integer} c
# @return {Integer}
def count_good_triplets(arr, a, b, c)
  count = 0
  size = arr.size
  
  for i in (0..size-3)
    for j in (i+1..size-2)
      for k in (j+1..size-1)
        if (arr[i] - arr[j]).abs <= a
          if (arr[j] - arr[k]).abs <= b
            if (arr[i] - arr[k]).abs <= c
              count += 1 
            end
          end
        end
      end
    end
  end
 
 count
end

The range of values for index i is [0, size-3], j i [i+1, size-2] and k is [j+1, size-1]. You can see the j and k ranges are reduced as it makes progress, this is an example for reducing the domains of the range. The index i has to stop at size-3 otherwise the j and k indices will go out of bounds.

Building Blocks

  • Reducing the Domains of the Variables
  • Off by One Error
  • Out of Bounds Error