# 6ms, 99.92% - No hashmaps and no sorting, but may require a lot of space

• ``````/*  No hashmaps and no sorting, but may require
* a lot of memory if the range of numbers in nums[] is pretty big.
Basic idea - use integers from nums[] as indices
in a new array - call it histogram. Then number at
index x in this histogram would represent number of
elements in nums[] equal to x
*/
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Integer[] hist;
List<List<Integer>> ret;

ret = new ArrayList<List<Integer>>();
if (nums.length < 3)
return ret;

// Loop 1 - determine bounds [sMin,sMax]
// Any number from nums[] outside of these bounds
// cannot make a tulip (a,b,c) where a+b+c=0
Integer max1 = null, max2 = null, min1 = null, min2 = null;
for (int i = 0; i < nums.length; i++) {
if (i == 0) {
max1 = min1 = nums[0];
} else {

if (nums[i] < min1){
min2 = min1;
min1 = nums[i];
}
else if (min2 == null || nums[i] < min2)
min2 = nums[i];

if (nums[i] > max1){
max2 = max1;
max1 = nums[i];
}
else if (max2 == null || nums[i] > max2)
max2 = nums[i];
}
}

int sMin = Math.max(min1, 0 - max1 - max2);
int sMax = Math.min(max1, 0 - min1 - min2);
int offset = -sMin;
int size = sMax - sMin + 1;
if (size < 1)
return ret;
hist = new Integer[size];

// Loop 2 - build histogram - array with indices matching
// numbers from input nums[] array restricted to [sMin,sMax] range.
// This histogram has more elements than distinct set of valid input integers.
// Some elements of histogram are nulls since their indices are not present in nums[].
// Use offset to start array from 0
for (int i = 0; i < nums.length; i++) {
if (nums[i] < sMin || nums[i] > sMax)
continue;
if (null == hist[nums[i] + offset])
hist[nums[i] + offset] = 1;
else
hist[nums[i] + offset]++;

}

// Loop 3 - loop through histogram
// In the outer loop only consider negative numbers since
// at least one number in tulip (a,b,c) should be negative
// (excluding {0,0,0} case)
for (int i = 0;i - offset < 0;i++)
{
// number a from (a,b,c) isn't present in nums[]
if (null == hist[i])
continue;
// Nested loop to find 2 more numbers in the tulip that includes number i
// Consider only tulips with elements in non-descending order
for (int j = i;j < hist.length && (j <=  3 * offset - i - j);j++)
{
// Several validations:
// when tulip (a,b,c) includes 2 equal numbers a and b
if (j == i && hist[i]<2)
continue;
// when histogram doesn't have number j
if (null == hist[j])
continue;
// when third number in the tulip is missing or is out of bound
if (3*offset - i - j < 0 || 3*offset - i - j >= size || null == hist[3*offset - i - j])
continue;
// when tulip (a,b,c) includes 2 equal numbers b and c
if ((j ==  3 * offset - i - j) && hist[j] < 2 )
continue;
// if we got here - add a valid tulip
ret.add(Arrays.asList(i - offset,j - offset, 2*offset - i - j));
}
}

// Handle case when array includes 3 zeros
if (null!= hist[offset] && hist[offset] >= 3)