Leetcode random challenge

cguy said:
As a brief explanation, the brute force approach goes through n values in the array, and for each one of these values (call it x) checks another n values to see if one of these values when added to the x, will equal the target. The inside part of the two for loops can run up to n*n times, so it is O(n*n). If you can avoid doing the second loop entirely, it will be O(n).

The purpose of the hash maps, is that they can look up the value "target - x", where x is the number for the current loop iteration, to see if it has been seen already in the current iteration - if it has, that value and the current value are the pair we want, and we are done. This lookup can be done without a loop (since hash maps typically have expected time O(1)).

What I did with the big "indexof" array, was essentially implement a very big, very fast hashmap, with worse case O(1) complexity, and a trivial hash function, so that it would be very fast. The downside of this, is that if the range of numbers was larger, the array could easily become too big, in which case, I would go for a more traditional hash map data structure.

Amusingly, the leading solution posted earlier did something similar, but must have submitted a bunch of times to narrow down the array range of the test set inputs as closely as possible.
Click to expand...
Yeah dude, your solution was badass. Nice
 
Cicero said:
Yeah dude, your solution was badass. Nice
Click to expand...

Thanks.

This was actually my solution that I finished off with:

Code: 
#include<inttypes.h>

int* twoSum(int* nums, int numsSize, int target) {
    int     tot=32768,mid=16384;
    short   indexofbase[tot];
    short * indexof = &indexofbase[mid];
    //int   * result = (int*)malloc(2*sizeof(int));
    static int64_t sr;
    int * result = (int*)&sr;
    int64_t * d = (int64_t*)indexofbase;
    for( int i=0; i < tot/32; i++ ) {
        d[ 0 ] = 0;
        d[ 1 ] = 0;
        d[ 2 ] = 0;
        d[ 3 ] = 0;
        d[ 4 ] = 0;
        d[ 5 ] = 0;
        d[ 6 ] = 0;       
        d[ 7 ] = 0;
        d += 8; // Clear 64 bytes per iteration
    }
    int num0 = nums[0];
    indexof[num0] = 0;
    int i=1;
    
    for( ; i + 3 < numsSize; i += 4 ) {
        int n0     = nums[i+0];
        int n1     = nums[i+1];
        int n2     = nums[i+2];
        int n3     = nums[i+3];
        int delta0 = target - n0;
        int delta1 = target - n1;
        int delta2 = target - n2;
        int delta3 = target - n3;
        if ( indexof[delta0] | (num0 == delta0) ) { result[0] = indexof[delta0]; result[1] = i+0; return result; }
        indexof[n0] = i+0;
        if ( indexof[delta1] | (num0 == delta1) ) { result[0] = indexof[delta1]; result[1] = i+1; return result; }
        indexof[n1] = i+1;
        if ( indexof[delta2] | (num0 == delta2) ) { result[0] = indexof[delta2]; result[1] = i+2; return result; }
        indexof[n2] = i+2;
        if ( indexof[delta3] | (num0 == delta3) ) { result[0] = indexof[delta3]; result[1] = i+3; return result; }
        indexof[n3] = i+3;
    }
    
    for( ; i < numsSize; i++ ) {
        int n     = nums[i];
        int delta = target - n;
        if ( indexof[delta] || num0 == delta ) {
            result[0] = indexof[delta];
            result[1] = i;
            return result;
        }
        indexof[n] = i;
    }
    return NULL;
}

This uses a smaller memory footprint, improves pipelining by unrolling the loops, factors out the check for i==0, and clears efficiently using an unrolled 64 byte/iteration using 8 instructions/iteration, it even uses a nasty hack to avoid doing any heap allocation (which can result in a system call) calls at all. It should really have been much faster than my first attempt, which makes me think that they are timing the launch time overhead, and that this is dominating the timing. Both this and my first attempt got 3ms.
 
Last edited:
cguy said:
As a brief explanation, the brute force approach goes through n values in the array, and for each one of these values (call it x) checks another n values to see if one of these values when added to the x, will equal the target. The inside part of the two for loops can run up to n*n times, so it is O(n*n). If you can avoid doing the second loop entirely, it will be O(n).

The purpose of the hash maps, is that they can look up the value "target - x", where x is the number for the current loop iteration, to see if it has been seen already in the current iteration - if it has, that value and the current value are the pair we want, and we are done. This lookup can be done without a loop (since hash maps typically have expected time O(1)).

What I did with the big "indexof" array, was essentially implement a very big, very fast hashmap, with worse case O(1) complexity, and a trivial hash function, so that it would be very fast. The downside of this, is that if the range of numbers was larger, the array could easily become too big, in which case, I would go for a more traditional hash map data structure.

Amusingly, the leading solution posted earlier did something similar, but must have submitted a bunch of times to narrow down the array range of the test set inputs as closely as possible.
Click to expand...


Thanks thats awesome stuff.
 
Cicero.

Thank you for the help, haven't had a chance to try it out yet!
 
Here's a Swift run at this.

1st attempt, I hit the problem straight on using a single loop and memoization;
Time: 9ms (leet server)
"Your runtime beats 96.7 % of Swift submissions."

Note:
The leet server appears to be quite a bit load sensitive; as time's vary a bit between runs; plus its obvious no LLVM compiler optimisations are applied (e.g. Fast, Whole Module Optimisation), which makes quite a bit difference with Swift code. e.g. leet states my 1st attempt took 9ms; whereas repeating that offline with the same test data it runs sub 1ms (0,72ms).

PHP: 
func twoSum0(_ nums: [Int], _ target: Int) -> [Int] {
  var d = [Int: Int]()
  for (i, num) in nums.enumerated() {
    guard let key = d[target - num] else { d[num] = i; continue }
    return [key, i]
  }
  fatalError("No solution.")
}

For my second attempt I decided to tackle the problem using recursion, thunks and result composition; the solution is less concise, but it's fast. Basically it recursively tackles the problem over two thunks. The thunk's role is primarily to provide the tail call optimisation, but they're also quite fast. BTW The other benefit of thunks over standard recursion is the ability to cross communicate between thunks; in this case if 1 thunk finds the solution it changes the found variable; the other thunk then terminates on the next recursive .Call i.e. minimal wasted cycles.

Time: 2ms (leet server), and 0.05ms (local) with the same test set.
"Your runtime beats 100.00 % of Swift submissions."

PHP: 
enum Result<E,A> {
  case Done(A)
  case Call(E, A)
}

func trampoline<E, A>(with fn: @escaping (E, A) -> Result<E, A>) -> ((E, A) -> A) {
  return { (value: E, accumulator: A) -> A in
    var result = fn(value, accumulator)
    while true {
      switch result {
      case let .Done(accumulator):
        return accumulator
      case let .Call(number, accumulator):
        result = fn(number, accumulator)
      }
    }
  }
}

func twoSum(_ nums: [Int], _ target: Int) -> [Int]
{
  let c = nums.count, m = c / 2
  var found = false
  let twoSumR = trampoline(with: { (n: (Int, Int), array: [Int]) -> Result<(Int, Int), [Int]> in
    guard n.0 < c && n.1 < c else { return .Done([]) }
    if target - nums[n.0] - nums[n.1] == 0 { found = true; return .Done([n.0, n.1]) }
    if n.0 == m - 1 || n.0 == c - 2 || found { return .Done([]) }
    if n.1 >= c - 2 { return .Call((n.0 + 1, n.0 + 2), array)}
    return .Call((n.0, n.1 + 1), array)
  })
  return c < 3 ? nums : twoSumR((0, 1), []) + twoSumR((m, m + 1), [])
}
 
Last edited:
[)roi(];20049272 said:
/snip
Click to expand...
Impressive [)roi(], welcome to the challenge...great time there.

I agree the timing is not exactly 100% accurate, but when you say offline/local, you can't be running the same test set because there are 19 tests it runs for the Two Sum (waaaay more for some others), and the time taken is some combination of all of those - be it a sum of all times, some weighted avg, who knows. Unless you managed to get hold of the entire 19 tests of course, in which case well played :D
 
Cicero said:
Impressive [)roi(], welcome to the challenge...great time there.

I agree the timing is not exactly 100% accurate, but when you say offline/local, you can't be running the same test set because there are 19 tests it runs for the Two Sum (waaaay more for some others), and the time taken is some combination of all of those - be it a sum of all times, some weighted avg, who knows. Unless you managed to get hold of the entire 19 tests of course, in which case well played :D
Click to expand...
Re offline tests, it's pretty much the same 19 tests (well at least most of them, some of the bigger ones I simply double up to make up the difference):
 
Last edited:
[)roi(];20049272 said:
Here's a Swift run at this.

1st attempt, I hit the problem straight on using a single loop and memoization;
Time: 9ms (leet server)
"Your runtime beats 96.7 % of Swift submissions."

Note:
The leet server appears to be quite a bit load sensitive; as time's vary a bit between runs; plus its obvious no LLVM compiler optimisations are applied (e.g. Fast, Whole Module Optimisation), which makes quite a bit difference with Swift code. e.g. leet states my 1st attempt took 9ms; whereas repeating that offline with the same test data it runs sub 1ms (0,72ms).

PHP: 
func twoSum0(_ nums: [Int], _ target: Int) -> [Int] {
  var d = [Int: Int]()
  for (i, num) in nums.enumerated() {
    guard let key = d[target - num] else { d[num] = i; continue }
    return [key, i]
  }
  fatalError("No solution.")
}

For my second attempt I decided to tackle the problem using recursion, thunks and result composition; the solution is less concise, but it's fast. Basically it recursively tackles the problem over two thunks. The thunk's role is primarily to provide the tail call optimisation, but they're also quite fast. BTW The other benefit of thunks over standard recursion is the ability to cross communicate between thunks; in this case if 1 thunk finds the solution it changes the found variable; the other thunk then terminates on the next recursive .Call i.e. minimal wasted cycles.

Time: 2ms (leet server), and 0.05ms (local) with the same test set.
"Your runtime beats 100.00 % of Swift submissions."

PHP: 
enum Result<E,A> {
  case Done(A)
  case Call(E, A)
}

func trampoline<E, A>(with fn: @escaping (E, A) -> Result<E, A>) -> ((E, A) -> A) {
  return { (value: E, accumulator: A) -> A in
    var result = fn(value, accumulator)
    while true {
      switch result {
      case let .Done(accumulator):
        return accumulator
      case let .Call(number, accumulator):
        result = fn(number, accumulator)
      }
    }
  }
}

func twoSum(_ nums: [Int], _ target: Int) -> [Int]
{
  let c = nums.count, m = c / 2
  var found = false
  let twoSumR = trampoline(with: { (n: (Int, Int), array: [Int]) -> Result<(Int, Int), [Int]> in
    guard n.0 < c && n.1 < c else { return .Done([]) }
    if target - nums[n.0] - nums[n.1] == 0 { found = true; return .Done([n.0, n.1]) }
    if n.0 == m - 1 || n.0 == c - 2 || found { return .Done([]) }
    if n.1 >= c - 2 { return .Call((n.0 + 1, n.0 + 2), array)}
    return .Call((n.0, n.1 + 1), array)
  })
  return c < 3 ? nums : twoSumR((0, 1), []) + twoSumR((m, m + 1), [])
}
Click to expand...

@[)roi(]

Could you try your solution in Go? I am really curious as to the performance difference (especially locally).

Your blog (codefunc.github.io) hasn't had any updates lately, would you be kind enough to add articles with your leetcode solutions explained in-depth? I for one would definitely read them. :)
 
Johnatan56 said:
@[)roi(]

Could you try your solution in Go? I am really curious as to the performance difference (especially locally).

Your blog (codefunc.github.io) hasn't had any updates lately, would you be kind enough to add articles with your leetcode solutions explained in-depth? I for one would definitely read them. :)
Click to expand...
As it happens, I'm coming out of the tail end of very a busy period; and surprisingly enough have been mulling over a revamp of the site; with a series of articles dedicated to (no surprise); Functional Programming (FP).

My primary goal is still to try to make it easier for anyone start with FP; because unlike OOP; FP is still relatively new paradigm in most programming circles, and whilst aspects of FP (like map, flatMap, reduce) are regularly used, the broader concepts of FP still eludes many. So this time round I'm going to try a different approach: starting with a basic concept like Magma, to indirectly reveal how this leads to map, flatMap, reduce, but more so how one atomic concept leads into the next, for example:
  • Magma -> Semigroup -> Morphism -> Monoid -> Functor -> Applicative Functor -> Monad -> Lenses / Prisms -> Futures, ...
The goal being to try to demonstrate not only how we use these small atomic concepts to compose more complex ones, but also what problems they address, and ultimately how these lead to parts of an application.

Basically in OOP; it's always going to be difficult to understand patterns if you don't appreciate the problem that they were designed to fix. The same applies with FP; the only difference being that with FP the problems being tackled tend to be far smaller ones e.g. null pointer exceptions.

...as for your request: Trampolines (thunk calls); I'll certainly try my best to incorporate that at a point. Anyway I'll notify on MyBB once some of it's ready.
 
Last edited:
Ok, now you get the gist...new week, new challenge:

17/07/2017 - 24/07/2017

42. Trapping Rain Water (labelled 'hard') - https://leetcode.com/problems/trapping-rain-water/#/description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
Click to expand...

Good luck!
 
To make it easier to understand, the image:

rainwatertrap.png
 
I should really get Go up and running again. Anyway, Java + regex:

Probably not the best way to solve it, but I felt like regex. C# would've made this "cleaner".

Code: 
public static int countVolume (List<Integer> levels) {

    String currentLevels = String.join("", levels.stream().map(x -> x.toString()).collect(Collectors.toList()));
    int volumeCount = 0;
    int baseValue = 0;

    while (!currentLevels.isEmpty()) {

      // if top reached
      if (currentLevels.replaceAll(Integer.toString(baseValue), "").isEmpty())
        break;

      // replace leading/trailing base values
      currentLevels = new StringBuilder(currentLevels.replaceFirst("^" + baseValue + "+(?!$)", "")).reverse().toString().replaceFirst("^" + baseValue + "+(?!$)", "");

      // count at base level
      Matcher m = Pattern.compile(Integer.toString(baseValue)).matcher(currentLevels);
      while (m.find())
        volumeCount++;

      // "flood" the base level
      currentLevels = currentLevels.replaceAll(Integer.toString(baseValue), Integer.toString(baseValue + 1));
      baseValue++;
    }

    return volumeCount;
  }
 
Hamster said:
I should really get Go up and running again. Anyway, Java + regex:

Probably not the best way to solve it, but I felt like regex. C# would've made this "cleaner".

Code: 
public static int countVolume (List<Integer> levels) {

    String currentLevels = String.join("", levels.stream().map(x -> x.toString()).collect(Collectors.toList()));
    int volumeCount = 0;
    int baseValue = 0;

    while (!currentLevels.isEmpty()) {

      // if top reached
      if (currentLevels.replaceAll(Integer.toString(baseValue), "").isEmpty())
        break;

      // replace leading/trailing base values
      currentLevels = new StringBuilder(currentLevels.replaceFirst("^" + baseValue + "+(?!$)", "")).reverse().toString().replaceFirst("^" + baseValue + "+(?!$)", "");

      // count at base level
      Matcher m = Pattern.compile(Integer.toString(baseValue)).matcher(currentLevels);
      while (m.find())
        volumeCount++;

      // "flood" the base level
      currentLevels = currentLevels.replaceAll(Integer.toString(baseValue), Integer.toString(baseValue + 1));
      baseValue++;
    }

    return volumeCount;
  }
Click to expand...
Awesome Hamster, whats your time and % submissions beaten with this?
 
If you guys are going to do this every week, then perhaps you should make a new post with a week identifier?

That way guys can still play with and add onto old posts, as well as see where/when a new one begins?
 
Cicero said:
Awesome Hamster, whats your time and % submissions beaten with this?
Click to expand...

Not sure I follow. You mean on leetcode? Don't think I have an account. Was just trying to solve it a "different" way :p

EDIT: OK, I ran it on leetcode and it bombs at test 314/315 because the code assumes there won't be any double digit numbers and will treat 10 as a 1 and a 0.
 
Last edited:
animal531 said:
If you guys are going to do this every week, then perhaps you should make a new post with a week identifier?

That way guys can still play with and add onto old posts, as well as see where/when a new one begins?
Click to expand...
Ok, I can do that. I agree it'll be easier to follow and contribute. I'll start doing that from next week.

Hamster said:
Not sure I follow. You mean on leetcode? Don't think I have an account. Was just trying to solve it a "different" way :p

EDIT: OK, I ran it on leetcode and it bombs at test 314/315 because the code assumes there won't be any double digit numbers and will treat 10 as a 1 and a 0.
Click to expand...
Haha, well then it doesn't count! /jk

My first quick lunchtime attempt completed all the tests on leetcode, but wasn't accepted because of 'Time limit exceeded', haha. It was a nasty solution though. Will give it another try after work.
 
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
Screen Shot 2017-07-18 at 7.07.23 PM.png
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.
 
I submitted the same code as C, C++ and C# and achieved 6ms, 9ms, 160ms.
The C# timing varies wildly per submission.

Code: 
class Solution {
public:
    int trap(vector<int>& height) {
        int firstRain = 0;
        int secondRain = 0;
        int localRain = 0;
        int previousHigh = 0;
        int highestPosition = 0;
        int length = height.size();
        int lastPosition = length-1;

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

        previousHigh = 0;
        localRain = 0;

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

        return firstRain + secondRain;
    }
};

TrappingWater_C.PNG
TrappingWater.PNG
 
Last edited:
Hamster said:
I should really get Go up and running again. Anyway, Java + regex:

Probably not the best way to solve it, but I felt like regex. C# would've made this "cleaner".

Code: 
    String currentLevels = String.join("", levels.stream().map(x -> x.toString()).collect(Collectors.toList()));
Click to expand...

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


n00b :p
 
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X