Skip to main content
Mapagam

Recognizing Array and Pointer Pattern Signals

1. Analyzing Problem Description

Signal Description Indicators Common Patterns
Array Input Problem involves an array or list of elements int[] nums, String[] arr Sorting, searching, subarray problems
Pointer Usage Requires two or more pointers to traverse data int left = 0; int right = nums.length - 1; Two sum, sliding window, merge intervals
Index-Based Access Accessing elements by index or position nums[i], arr[index] Two sum, container with most water
Subarray/Sublist Problem asks for a contiguous portion of array max subarray sum, longest substring Kadane's algorithm, sliding window
Duplicate Elements Problem involves checking or handling duplicates nums[i] == nums[j] Remove duplicates, valid anagram
Sorted Input Array is already sorted or can be sorted int[] sorted = Arrays.sort(nums) Binary search, three sum

Example: Two Sum Problem

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}
Note: The problem description often hints at the need for a two-pointer approach or hash map solution.

2. Evaluating Input Constraints

Constraint Description Implication Pattern Match
Sorted Input Array elements are in ascending or descending order Binary search or two-pointer techniques may apply if (arr[i] <= arr[i+1])
Fixed Size Array length is known and unchanging Direct indexing and loop bounds are safe for (let i = 0; i < arr.length; i++)
Unique Elements All elements in array are distinct Can use hash maps or sets for O(1) lookups new Set(arr)
Duplicate Elements Some elements appear more than once Need to handle frequency or grouping logic Map<number, number>
Large Input Size Array size exceeds typical memory limits Consider streaming or divide-and-conquer approaches chunked processing
Small Input Size Array size is small (e.g., < 10 elements) Simple brute-force solutions may be acceptable O(n^2) for small n

Example: Detecting Sorted Input

function isSorted(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) return false;
  }
  return true;
}

Example: Using Set for Unique Elements

function hasUniqueElements(arr) {
  const seen = new Set();
  for (const item of arr) {
    if (seen.has(item)) return false;
    seen.add(item);
  }
  return true;
}

3. Identifying Data Structure Type

Pattern Description Indicators Common Use Cases
Array Sequential collection of elements with indexed access arr[i], length, push/pop Storing lists, implementing stacks/queues
Linked List Elements connected via pointers, not indexed node.next, head, tail Dynamic memory allocation, efficient insertions/deletions
Stack LIFO (Last In, First Out) structure push/pop, top Function call management, undo operations
Queue FIFO (First In, First Out) structure enqueue/dequeue, front/rear Task scheduling, breadth-first search
Hash Table Key-value pairs with fast lookups hash(key), get/set Caching, indexing, symbol tables
Tree Hierarchical structure with parent-child relationships root, node.left/right File systems, expression parsing, decision trees
Graph Collection of nodes connected by edges adjacency list/matrix, node.edges Social networks, routing algorithms, dependency resolution

Example: Detecting Array vs Linked List

const arr = [1, 2, 3];
const list = new Node(1);
list.next = new Node(2);
list.next.next = new Node(3);

// Array - O(1) random access
console.log(arr[2]); // 3

// Linked List - O(n) traversal to access
let current = list;
for (let i = 0; i < 2; i++) {
  current = current.next;
}
console.log(current.value); // 3

4. Recognizing Sorted Array Signal

When an array is sorted in ascending or descending order, it often indicates that the problem can be solved more efficiently using binary search or two-pointer techniques.

Signal Description Implication
Ascending Order Elements are in non-decreasing order: a[i] <= a[i+1] Binary search can be applied for efficient lookups
Descending Order Elements are in non-increasing order: a[i] >= a[i+1] Binary search can be adapted for reverse lookup
Partially Sorted Some elements are in sorted order, others not May require hybrid approaches or preprocessing

Example: Detecting Sorted Array

function isSorted(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) return false;
  }
  return true;
}

// Example usage:
const sortedArray = [1, 2, 3, 4, 5];
const unsortedArray = [1, 3, 2, 4, 5];

console.log(isSorted(sortedArray)); // true
console.log(isSorted(unsortedArray)); // false
Note: A sorted array allows for O(log n) time complexity in searching operations using binary search.

5. Recognizing Pair/Triplet Sum Signal

Signal Type Description Common Patterns Examples
Two Sum Find two elements that sum to a target value Use hash map for O(1) lookup 
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
}
Three Sum Find three elements that sum to zero or target Sort array and use two pointers for O(n) search 
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
  return result;
}
K Sum Generalization of Two/Three Sum to K elements Use recursion or iterative approach with hash maps 
function kSum(nums, target, k) {
  if (k === 2) return twoSum(nums, target);
  // Recursive or iterative implementation
}
Note: For Three Sum, sorting the array allows for efficient two-pointer technique, reducing time complexity from O(n^3) to O(n^2).

6. Recognizing Contiguous Subarray/Substring Signal

Signal Description Common Indicators Examples
Contiguous Elements Elements that appear sequentially in memory or array nums[i], nums[i+1], nums[i+2] 
const arr = [1, 2, 3, 4, 5];
// Subarray: [2, 3, 4]
Fixed Size Window Operations on a fixed-size sliding window k elements at a time 
const windowSize = 3;
// Sliding window over [1,2,3,4,5] with size 3
Variable Size Window Window size changes dynamically based on conditions Expanding or shrinking window 
let left = 0, right = 0;
while (right < arr.length) {
  // Expand window
  if (condition) right++;
  else left++; // Shrink window
}
Substring Match Need to find a substring matching criteria Pattern matching, character count 
const s = "abcabcbb";
// Find longest substring without repeating chars
Sum of Subarray Need to compute sum of a contiguous subarray Prefix sums, cumulative sums 
const prefixSum = [0];
for (let i = 0; i < arr.length; i++) {
  prefixSum[i+1] = prefixSum[i] + arr[i];
}

Example: Sliding Window for Maximum Sum Subarray

function maxSubarraySum(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  // Calculate sum of first window
  for (let i = 0; i < k; i++) {
    windowSum += arr[i];
  }

  maxSum = windowSum;

  // Slide the window from left to right
  for (let i = k; i < arr.length; i++) {
    windowSum = windowSum - arr[i - k] + arr[i];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

// Example usage:
const nums = [2, 1, 5, 1, 3, 2];
console.log(maxSubarraySum(nums, 3)); // Output: 9

Example: Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
  const charIndexMap = new Map();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    const currentChar = s[right];

    if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
      left = charIndexMap.get(currentChar) + 1;
    }

    charIndexMap.set(currentChar, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

// Example usage:
const str = "abcabcbb";
console.log(lengthOfLongestSubstring(str)); // Output: 3
Note: The sliding window technique is particularly effective for problems where the solution involves a contiguous subsequence and can be optimized using a two-pointer approach.

7. Recognizing Linked List + Cycle Signal

Signal Description Indicators
Slow/Fast Pointer Movement Use of two pointers moving at different speeds
  • One pointer moves one step at a time
  • Another moves two steps at a time
Meeting Point Point where slow and fast pointers meet
  • Indicates a cycle in the list
  • Used to detect loop presence
Cycle Length Distance between meeting point and start of cycle
  • Can be calculated once the meeting point is found
  • Used to find the start of the cycle

Example: Detecting Cycle in Linked List

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head) {
  if (!head || !head.next) return false;

  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true; // Cycle detected
    }
  }

  return false;
}
Note: The Floyd's Cycle Detection Algorithm (also known as the "Tortoise and Hare" algorithm) uses two pointers moving at different speeds to detect cycles in a linked list.

8. Recognizing Missing/Duplicate in Range Signal

Signal Description Common Patterns Examples
Missing Element in Range One element from a known range is missing Sum formula, XOR operation, Binary search 
const nums = [1, 2, 4, 5]; // Missing 3
const n = nums.length;
const expectedSum = (n + 1) * (n + 2) / 2;
const actualSum = nums.reduce((a, b) => a + b, 0);
const missing = expectedSum - actualSum;
Duplicate Element in Range One element appears twice in a known range Set-based detection, Sorting, XOR operation 
const nums = [1, 2, 3, 3, 4]; // Duplicate 3
const seen = new Set();
for (let num of nums) {
  if (seen.has(num)) {
    console.log("Duplicate found:", num);
    break;
  }
  seen.add(num);
}

Example: Finding Missing Number in Range

const nums = [0, 1, 3, 4, 5];
const n = nums.length;
let expectedSum = (n * (n + 1)) / 2;
let actualSum = nums.reduce((a, b) => a + b, 0);
let missing = expectedSum - actualSum;
console.log(missing); // 2

Example: Detecting Duplicate in Range

const nums = [1, 2, 3, 3, 4];
let seen = new Set();
for (let num of nums) {
  if (seen.has(num)) {
    console.log("Duplicate:", num);
    break;
  }
  seen.add(num);
}

9. Recognizing Monotonic Function Signal

Signal Type Description Indicators Use Case
Monotonic Increasing Function values never decrease as input increases f(x) <= f(y) for all x < y Sorting, optimization problems
Monotonic Decreasing Function values never increase as input increases f(x) >= f(y) for all x < y Binary search, optimization problems
Strictly Monotonic Function values strictly increase or decrease f(x) < f(y) for all x < y Binary search, uniqueness validation

Example: Detecting Monotonic Function

function isMonotonic(arr) {
  let increasing = true;
  let decreasing = true;

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) increasing = false;
    if (arr[i] > arr[i - 1]) decreasing = false;
  }

  return increasing || decreasing;
}

// Example usage:
const nums1 = [1, 2, 3, 4, 5];
const nums2 = [5, 4, 3, 2, 1];
const nums3 = [1, 3, 2, 4];

console.log(isMonotonic(nums1)); // true
console.log(isMonotonic(nums2)); // true
console.log(isMonotonic(nums3)); // false
Note: Monotonic functions are key in binary search optimizations and sorting algorithms.

Was this article helpful?

Related Cheat Sheets