Sort 3 Integers without using if condition (use only Max())

Problem

Given three integers a, b, and c, sort them in non-decreasing order without using any if/conditional branching. The allowed primitive is the max() function (and arithmetic).

Examples

Example 1

1
2
3
4
5
6
7
8

Input:
a = 4, b = 1, c = 9

Output:
[1, 4, 9]

Explanation:
Using only `max()` and arithmetic we compute min, mid and max.

Example 2

1
2
3
4
5
6
7
8

Input:
a = 5, b = 5, c = 2

Output:
[2, 5, 5]

Explanation:
Duplicates are handled naturally by the formulas.

Solution

Method 1 - Use Max() and arithmetic

Intuition

We can compute the maximum with max(a, max(b, c)). The minimum can be computed by negating all values and taking a max: min = -max(-a, -b, -c). The middle value follows from mid = a + b + c - max - min.

Approach

  1. Compute max = max(a, max(b, c)).
  2. Compute min = -max(-a, -b, -c).
  3. Compute mid = a + b + c - max - min.
  4. Return [min, mid, max].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include <algorithm>
#include <array>
using namespace std;

class Solution {
 public:
  array<int, 3> sort3(int a, int b, int c) {
    int mx = max(a, max(b, c));
    int mn = -max(-a, max(-b, -c));
    int mid = a + b + c - mx - mn;
    return {mn, mid, mx};
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

func sort3(a, b, c int) [3]int {
    mx := max(a, max(b, c))
    mn := -max(-a, max(-b, -c))
    mid := a + b + c - mx - mn
    return [3]int{mn, mid, mx}
}

func max(x, y int) int { if x > y { return x }; return y }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.Arrays;

class Solution {
  public int[] sort3(int a, int b, int c) {
    int mx = Math.max(a, Math.max(b, c));
    int mn = -Math.max(-a, Math.max(-b, -c));
    int mid = a + b + c - mx - mn;
    return new int[]{mn, mid, mx};
  }
}
1
2
3
4
5
6
7
8

class Solution {
  fun sort3(a: Int, b: Int, c: Int): IntArray {
    val mx = maxOf(a, maxOf(b, c))
    val mn = -maxOf(-a, maxOf(-b, -c))
    val mid = a + b + c - mx - mn
    return intArrayOf(mn, mid, mx)
  }
}
1
2
3
4
5
6
7
8

from typing import List

class Solution:
  def sort3(self, a: int, b: int, c: int) -> List[int]:
    mx = max(a, max(b, c))
    mn = -max(-a, max(-b, -c))
    mid = a + b + c - mx - mn
    return [mn, mid, mx]
1
2
3
4
5
6
7
8
9

pub struct Solution;
impl Solution {
  pub fn sort3(a: i32, b: i32, c: i32) -> [i32; 3] {
    let mx = std::cmp::max(a, std::cmp::max(b, c));
    let mn = -std::cmp::max(-a, std::cmp::max(-b, -c));
    let mid = a + b + c - mx - mn;
    [mn, mid, mx]
  }
}
1
2
3
4
5
6
7
8

export class Solution {
  sort3(a: number, b: number, c: number): number[] {
    const mx = Math.max(a, Math.max(b, c));
    const mn = -Math.max(-a, Math.max(-b, -c));
    const mid = a + b + c - mx - mn;
    return [mn, mid, mx];
  }
}

Complexity

  • ⏰ Time complexity: O(1) – A constant number of arithmetic and max() operations.
  • 🧺 Space complexity: O(1) – Only a few local variables are used.