Leetcode random challenge

_kabal_ said:
Code: 
   String currentLevels = levels.stream().map(Object::toString).reduce("", (a, b) -> a + b);


n00b :p
Click to expand...

Indeed :D

I'm gonna blame it on something like me having flu cos I swear I'm awesome when I'm healthy :p
 
In C - 6ms, beats 46.3% of submissions, can't get it quicker unfortunately.

Code: 
int trap(int* height, int heightSize) {  
    int i, j, h, gnd, water, maxH;
    
    /* Dont care abt zero's */
    for (j=0; j<heightSize; j++) {
        h = height[j];
        if (h) break;
    }
    
    water = 0;
    maxH = 0;
    gnd = 0;
    for (i=j+1; i<heightSize; i++) {
        if (height[i] >= h) {
            water += ((i-j-1)*h - gnd);  /* area - gnd */            
            /* continue from here */
            h = height[i]; 
            j = i;
            gnd = 0;
            maxH = 0;
        } else {
            gnd+=height[i];
            if (height[i] > maxH) maxH=height[i];
            if (gnd && ((i+1)==heightSize)) {
                /* Got to the end, and didn't find anyhting as big as h
                    restart with new height maxH */
                i=j;
                h = maxH; 
                gnd = 0;
                maxH = 0;
            }
        }
    }
    return water;
}

I had a couple of other attempts, but none could get quicker.
Recursion which the above was based off, bit nasty, also at 6ms:
Code: 
int trap(int* height, int heightSize) {  
    int gnd, i, j, h, water, maxH;
    
    water = 0;
    
    for (j=0; j<heightSize; j++) {
        h = height[j];
        if (h) break;
    }
    
    maxH = 0;
    gnd = 0;
    for (i=j+1; i<heightSize; i++) {
        if (height[i] >= h) {
            water+=((i-j-1)*h - gnd);
            water+=trap(&height[i], heightSize-i);
            break;
        } else {
            gnd+=height[i];
            if (height[i] > maxH) maxH=height[i];
            if (gnd && ((i+1)==heightSize)) {
                height[j] = maxH;
                water+=trap(&height[j], heightSize-(j));
            }
        }
    }
    return water;
}

And my first quick lunchtime attempt on Monday which was really inefficient and resulted in a "time limit exceeded", haha
Code: 
int trap(int* height, int heightSize) {  
    int i, j, h, water;
    
    water = 0;
    
    int heightIndex[35000];
    
    memset(heightIndex,0,35000*sizeof(int));

    for (i=0; i<heightSize; i++) {
        h = height[i];
        if (!h) continue;
        for(j=0; j < h; j++) {            
            if (heightIndex[j]) {
                water += (i-heightIndex[j]);
            }
            heightIndex[j] = i+1;
        }            
    }    
    return water;
}
 
[)roi(];20071158 said:
First run at this is an iterative version that narrows inwards; comparing left and right heights.

PHP: 
    func trap(_ height: [Int]) -> Int {
      var values = (left: 0, right: height.count - 1, level: 0, water: 0)
      while values.left < values.right {
        var lowerIndex = 0
        if height[values.left] < height[values.right] {
          lowerIndex = values.left
          values.left += 1
        }
        else
        {
          lowerIndex = values.right
          values.right -= 1
        }
        let lowerLevel = height[lowerIndex]
        values.level = max(values.level, lowerLevel)
        values.water += values.level - lowerLevel
      }
      return values.water
    }

Time: 17ms
View attachment 449444
Again leet server times are less than ideal (quite a bit of load related variation); FYI repeating the same volume of tests locally (315) runs sub 1ms.

A functional version using map and reduce is also possible; but doubtful it could achieve a faster time, without left/right concurrency.
Click to expand...
Missed your post. "Beats 100% of swift submissions", that's pretty decent, lol.

How do you get your hands on their full test set?
 
Last edited:
Cicero said:
Missed your post. "Beats 100% of swift submissions", that's pretty decent, lol.
Click to expand...
No worries.

Here's another to prove the notion that almost anything can be done in reducer; and its only marginally slower (sub ms) than an iterative version:
PHP: 
func trap(_ height: [Int]) -> Int
{
  return height.indices
    .reduce((level: 0, water: 0, s: 0, e: height.count - 1, lower: 0)) {
      var (level, water, s, e, lower) = $0.0 // Tuple splat for mutability
      if s >= e { return $0.0 }
      if height[s] < height[e] { lower = height[s]; s += 1 }
      else { lower = height[e]; e -= 1 }
      level = max(level, lower)
      return (level, water + level - lower, s, e, lower)
    }.water
}

...and for the really awful here's multiple reducers (left / right sweeps & then combine); this one certainly isn't going to win any records, but with larger datasets it could be converted to transducers and to run the sweeps concurrently.
PHP: 
func trap(_ height: [Int]) -> Int
{
  let last = height.count - 1
  let initial = (left: (max: height[0], array: [height[0]]),
                 right: (max: height[last], array: [height[last]]))
  let comb = (1...last).reduce(initial) {
    let l = (height[$0.1] < $0.0.left.max) ?
      ($0.0.left.max, $0.0.left.array + [$0.0.left.max]) :
      (height[$0.1], $0.0.left.array + [height[$0.1]])
    
    let r = (height[last - $0.1] < $0.0.right.max) ?
      ($0.0.right.max, [$0.0.right.max] + $0.0.right.array) :
      (height[last - $0.1], [height[last - $0.1]] + $0.0.right.array)
    return (left: l, right: r)
  }
  
  return height.indices.reduce(0) {
    let trap = min(comb.left.array[$0.1], comb.right.array[$0.1]) - height[$0.1]
    return trap > 0 ? $0.0 + trap : $0.0
  }
}
 
[)roi(];20076784 said:
/snip
Click to expand...
Wtf...Swift (which I presume that is) blows my mind, I literally can't follow a thing there :erm:

Not sure whether to laugh or cry when I (try) read it.
 
Here's a python one:

Code: 
# Runtime: 56 ms
# Your runtime beats 48.39 % of python submissions.

class Solution(object):

    def trap(self, height):
        leftVals = self.traverse(height)
        rightVals = self.traverse(height[::-1])[::-1]
        volume = 0
        for i in range(len(height)):
            volume += min(leftVals[i], rightVals[i])
        return volume

    def traverse(self, height):
        maxVals = [0]*len(height)
        currentMax = 0
        for i, currentHeight in enumerate(height):
            if currentHeight > currentMax:
                currentMax = max(currentMax, currentHeight)
            else:
                maxVals[i] = currentMax-currentHeight
        return maxVals
 
Cicero said:
Wtf...Swift (which I presume that is) blows my mind, I literally can't follow a thing there :erm:

Not sure whether to laugh or cry when I (try) read it.
Click to expand...
It's tough to read if you're unfamiliar with reducers and Swift's tuple syntax. As for the reducer, it's internal makeup is a fairly standard iterative loop that takes an initial value, and passes in an element, and then accumulates values between each iteration.

Here's a simple reducer to sum the values from 1 to 100:
PHP: 
let answer = (1...100).reduce(0) { $0 + $1 } // the curly braces are the reducer's closure, and the 0 is then initial value to load the accumulator

// That can even be syntactical reduced to:
let answer = (1...100).reduce(0, +)  // Implicit tuple splat (accumulator & element), passed to + operator

// The equivalent iterative C version would look something like this:

int answer = sum(0, 1, 100);

int sum(int initial, int start, int end) // initial is the identity value
{
  int accumulator = initial;
  for (int element = 1; element <= 100; element++)
  {
    accumulator += element; // this is closure part in the reducer
  }
  return accumulator;
}

Basically this is a tuple that wraps (Int, Int, Int, Int, Int): (similar to a class or struct with 5 properties)
PHP: 
(level: 0, water: 0, s: 0, e: height.count - 1, lower: 0)

In a closure; $0 refers to 1st value being passed in i.e. 1st argument. Whereas $0.0 refers the 1st tuple value of the 1st argument, assuming the 1st argument is a tuple. Which with a reducer is a tuple of (accumulator & element). So basically $0.0 referred to the tuple of 5 Ints (the accumulator) and $0.1 refer to the next element from the enumerator.

Btw tuples and reducers aren't unique to Swift; C++ (std::tuple), C# (Tuple class), Python, ... all have them.
 
Last edited:
Times so far for 42) Trapping Rain Water

Swift
  • [)roi(] - 17ms (beats 100% of Swift submissions)

C
  • Dan - 6ms (beats 46.43%)
  • Cicero - 6ms

C++
  • DanH - 9ms (beats 63.6%)

C#
  • DanH - 160ms

Python
  • Hamster - 56ms (beats 48.39%)
 
Cicero said:
Times so far for 42) Trapping Rain Water

Swift
  • [)roi(] - 17ms (beats 100% of Swift submissions)

C
  • Dan - 6ms (beats 46.43%)
  • Cicero - 6ms

C++
  • DanH - 9ms (beats 63.6%)

C#
  • DanH - 160ms

Python
  • Hamster - 56ms (beats 48.39%)
Click to expand...
Cool; but I'd argue that the ms report is really pointless for profiling across languages.
C vs C is fine, but C vs C# is open to a minefield of technicalities (none of which are priorities for leet); basically in the above example the 9ms for C++ is far less relevant than the 63.6% of submissions it bested.
 
Haven't coded Go in a while, but decided to do the exact same thing I did in Python just to check the difference:

Code: 
func trap(height []int) int {

	leftMaxVals := make([]int, len(height))
	leftCurrentMax := 0
	for i := 0; i < len(height); i++ {
		if height[i] > leftCurrentMax {
			leftCurrentMax = height[i]
		} else {
			leftMaxVals[i] = leftCurrentMax - height[i]
		}
	}

	rightMaxVals := make([]int, len(height))
	rightCurrentMax := 0
	for i := len(height) - 1; i >= 0; i-- {
		if height[i] > rightCurrentMax {
			rightCurrentMax = height[i]
		} else {
			rightMaxVals[i] = rightCurrentMax - height[i]
		}
	}

	volume := 0
	for i := range height {
		if leftMaxVals[i] < rightMaxVals[i] {
			volume += leftMaxVals[i]
		} else {
			volume += rightMaxVals[i]
		}
	}

	return volume
}

Runtime: 26 ms
Only beats 13.64 % of golang submissions though.
 
DanH said:
I submitted the same code as C, C++ and C# and achieved 6ms, 9ms, 160ms.
Click to expand...

Rewrote your solution in Go and got 12ms (beats 18.18% of Go submissions)

Code: 
func trap(height []int) int {
	firstRain := 0
	secondRain := 0
	localRain := 0
	previousHigh := 0
	highestPosition := 0

	for i := 0; i < len(height); i++ {
		if height[i] >= previousHigh {
			previousHigh = height[i]
			highestPosition = i
			firstRain = localRain
		} else {
			localRain += previousHigh - height[i]
		}
	}

	previousHigh = 0
	localRain = 0

	for i := len(height) - 1; i >= highestPosition; i-- {
		if height[i] >= previousHigh {
			previousHigh = height[i]
			secondRain = localRain
		} else {
			localRain += previousHigh - height[i]
		}
	}

	return firstRain + secondRain
}
 
[)roi(];20090804 said:
Cool; but I'd argue that the ms report is really pointless for profiling across languages.
C vs C is fine, but C vs C# is open to a minefield of technicalities (none of which are priorities for leet); basically in the above example the 9ms for C++ is far less relevant than the 63.6% of submissions it bested.
Click to expand...
I agree of course.

But my hope is that more people will join over time, and then the ms's will be a relevant mybb benchmark to those in the same language. Thats why I split the times by language, it'd be ridiculous for Hamster for example to get annoyed that he can only reach 56ms just because he's comparing that to the times in C.
 
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X