Write a function to find both the maximum and minimum values in a list of integers in a single pass (without using built-in max/min functions).

Overview

Finding both maximum and minimum values in a single pass is an optimization problem that demonstrates efficient algorithm design. While built-in functions exist, implementing this from scratch tests your understanding of linear search and comparison optimization.

Challenge: Find both max and min with minimum comparisons.

Approach 1: Single Pass (Optimal)

Track both max and min in one iteration.

dartCopy
Map<String, int> findMaxMin(List<int> nums) {
  if (nums.isEmpty) {
    throw ArgumentError('List cannot be empty');
  }

  int max = nums[0];
  int min = nums[0];

  for (int i = 1; i < nums.length; i++) {
    if (nums[i] > max) {
      max = nums[i];
    }
    if (nums[i] < min) {
      min = nums[i];
    }
  }

  return {'max': max, 'min': min};
}

void main() {
  print(findMaxMin([3, 1, 4, 1, 5, 9, 2, 6]));
  // {max: 9, min: 1}

  print(findMaxMin([42]));
  // {max: 42, min: 42}

  print(findMaxMin([-5, -2, -10, -1]));
  // {max: -1, min: -10}
}

Time Complexity: O(n) - single iteration Space Complexity: O(1) - only two variables Comparisons: 2(n-1) in worst case

Approach 2: Return as Tuple/Record

Using Dart 3.0 records for cleaner return type.

dartCopy
(int max, int min) findMaxMinRecord(List<int> nums) {
  if (nums.isEmpty) {
    throw ArgumentError('List cannot be empty');
  }

  int max = nums[0];
  int min = nums[0];

  for (int num in nums) {
    if (num > max) max = num;
    if (num < min) min = num;
  }

  return (max, min);
}

void main() {
  var (max, min) = findMaxMinRecord([3, 1, 4, 1, 5, 9, 2, 6]);
  print('Max: $max, Min: $min');  // Max: 9, Min: 1
}

Dart 3.0+ only - Uses modern record syntax.

Approach 3: Class-Based Result

Custom class for structured result.

dartCopy
class MaxMinResult {
  final int max;
  final int min;
  final int range;

  MaxMinResult(this.max, this.min) : range = max - min;

  @override
  String toString() => 'Max: $max, Min: $min, Range: $range';
}

MaxMinResult findMaxMinClass(List<int> nums) {
  if (nums.isEmpty) {
    throw ArgumentError('List cannot be empty');
  }

  int max = nums[0];
  int min = nums[0];

  for (int num in nums) {
    if (num > max) max = num;
    if (num < min) min = num;
  }

  return MaxMinResult(max, min);
}

void main() {
  var result = findMaxMinClass([3, 1, 4, 1, 5, 9, 2, 6]);
  print(result);  // Max: 9, Min: 1, Range: 8
  print('Range: ${result.range}');
}

Approach 4: Tournament Method (Fewer Comparisons)

Process pairs to reduce total comparisons.

dartCopy
Map<String, int> findMaxMinTournament(List<int> nums) {
  if (nums.isEmpty) {
    throw ArgumentError('List cannot be empty');
  }

  int max, min;

  // Initialize based on even/odd length
  int startIndex;
  if (nums.length % 2 == 0) {
    max = nums[0] > nums[1] ? nums[0] : nums[1];
    min = nums[0] < nums[1] ? nums[0] : nums[1];
    startIndex = 2;
  } else {
    max = min = nums[0];
    startIndex = 1;
  }

  // Process pairs
  for (int i = startIndex; i < nums.length - 1; i += 2) {
    int pairMax, pairMin;

    if (nums[i] > nums[i + 1]) {
      pairMax = nums[i];
      pairMin = nums[i + 1];
    } else {
      pairMax = nums[i + 1];
      pairMin = nums[i];
    }

    if (pairMax > max) max = pairMax;
    if (pairMin < min) min = pairMin;
  }

  return {'max': max, 'min': min};
}

void main() {
  print(findMaxMinTournament([3, 1, 4, 1, 5, 9, 2, 6]));
  // {max: 9, min: 1}
}

Time Complexity: O(n) Space Complexity: O(1) Comparisons: 3(n/2) ≈ 1.5n (25% fewer than simple approach)

Approach 5: Generic Implementation

Works with any comparable type.

dartCopy
class MinMax<T extends Comparable> {
  final T max;
  final T min;

  MinMax(this.max, this.min);

  @override
  String toString() => 'Max: $max, Min: $min';
}

MinMax<T> findMaxMinGeneric<T extends Comparable>(List<T> items) {
  if (items.isEmpty) {
    throw ArgumentError('List cannot be empty');
  }

  T max = items[0];
  T min = items[0];

  for (T item in items) {
    if (item.compareTo(max) > 0) max = item;
    if (item.compareTo(min) < 0) min = item;
  }

  return MinMax(max, min);
}

void main() {
  // Works with integers
  print(findMaxMinGeneric([3, 1, 4, 1, 5, 9]));
  // Max: 9, Min: 1

  // Works with strings
  print(findMaxMinGeneric(['apple', 'banana', 'cherry']));
  // Max: cherry, Min: apple

  // Works with doubles
  print(findMaxMinGeneric([3.14, 2.71, 1.41, 1.73]));
  // Max: 3.14, Min: 1.41
}

Complete Solution Class

dartCopy
class MaxMinFinder {
  // Basic implementation
  static Map<String, int> find(List<int> nums) {
    if (nums.isEmpty) throw ArgumentError('List cannot be empty');

    int max = nums[0];
    int min = nums[0];

    for (int num in nums) {
      if (num > max) max = num;
      if (num < min) min = num;
    }

    return {'max': max, 'min': min};
  }

  // With index tracking
  static Map<String, dynamic> findWithIndices(List<int> nums) {
    if (nums.isEmpty) throw ArgumentError('List cannot be empty');

    int max = nums[0], maxIndex = 0;
    int min = nums[0], minIndex = 0;

    for (int i = 1; i < nums.length; i++) {
      if (nums[i] > max) {
        max = nums[i];
        maxIndex = i;
      }
      if (nums[i] < min) {
        min = nums[i];
        minIndex = i;
      }
    }

    return {
      'max': max,
      'maxIndex': maxIndex,
      'min': min,
      'minIndex': minIndex,
    };
  }

  // Safe version with null handling
  static Map<String, int>? findSafe(List<int>? nums) {
    if (nums == null || nums.isEmpty) return null;
    return find(nums);
  }

  // With statistics
  static Map<String, dynamic> findWithStats(List<int> nums) {
    if (nums.isEmpty) throw ArgumentError('List cannot be empty');

    int max = nums[0];
    int min = nums[0];
    int sum = 0;

    for (int num in nums) {
      if (num > max) max = num;
      if (num < min) min = num;
      sum += num;
    }

    return {
      'max': max,
      'min': min,
      'range': max - min,
      'average': sum / nums.length,
    };
  }
}

void main() {
  var nums = [3, 1, 4, 1, 5, 9, 2, 6];

  print(MaxMinFinder.find(nums));
  // {max: 9, min: 1}

  print(MaxMinFinder.findWithIndices(nums));
  // {max: 9, maxIndex: 5, min: 1, minIndex: 1}

  print(MaxMinFinder.findWithStats(nums));
  // {max: 9, min: 1, range: 8, average: 3.875}

  print(MaxMinFinder.findSafe(null));
  // null

  print(MaxMinFinder.findSafe([]));
  // null
}

Comparison

Edge Cases

dartCopy
void testEdgeCases() {
  // Single element
  var single = findMaxMin([42]);
  assert(single['max'] == 42 && single['min'] == 42);

  // All same values
  var same = findMaxMin([5, 5, 5, 5]);
  assert(same['max'] == 5 && same['min'] == 5);

  // All negative
  var negative = findMaxMin([-5, -2, -10, -1]);
  assert(negative['max'] == -1 && negative['min'] == -10);

  // Extreme values
  var extreme = findMaxMin([0, 1000000, -1000000]);
  assert(extreme['max'] == 1000000 && extreme['min'] == -1000000);

  // Two elements
  var two = findMaxMin([10, 5]);
  assert(two['max'] == 10 && two['min'] == 5);
}

Best Practices

1. Handle Empty Lists

dartCopy
// ✅ Throw descriptive error
Map<String, int> findMaxMin(List<int> nums) {
  if (nums.isEmpty) {
    throw ArgumentError('Cannot find max/min of empty list');
  }
  // ... logic
}

2. Use Null Safety

dartCopy
// ✅ Return nullable result
Map<String, int>? findMaxMinSafe(List<int>? nums) {
  if (nums == null || nums.isEmpty) return null;
  // ... logic
}

3. Use Records for Modern Dart

dartCopy
// ✅ Dart 3.0+ - cleaner syntax
(int max, int min) findMaxMin(List<int> nums) {
  // ... logic
  return (max, min);
}

4. Document Complexity

dartCopy
/// Finds max and min in single pass.
///
/// Time: O(n), Space: O(1), Comparisons: 2(n-1)
Map<String, int> findMaxMin(List<int> nums) { ... }

Interview Tips

When asked about max/min:

1. Clarify if built-in allowed:

   • If yes:
     textCopy

     nums.reduce(max)

     ,
     textCopy

     nums.reduce(min)

   • If no: Implement from scratch

2. Mention single-pass optimization:

   • "We can find both in one iteration"
   • Discuss comparison count

3. Handle edge cases:

   • Empty list
   • Single element
   • All same values

4. Consider extensions:

   • Track indices
   • Calculate range/average
   • Generic implementation

Resources

• List.reduce - Dart API
• Comparable - Dart API
• Records - Dart Language