1 Problem, 24 Programming Languages 

Yes you should always use .iter() unless you need mutability and/or want to move the values somewhere else

I also thought that you can pass nums by reference (borrow it). Plus make it a slice instead of vector, so the solution become more general. fn maximum_count(nums: &[i32]) -> i32 { ...

Yea, this is way nicer! I tried using .iter() but clearly didn't set up the lambda correctly. Thanks : )

So much more sexy

@@code_report The problem with iter is that you get an extra reference (Iterator), instead of into_iter (Iterator), then in filter you take &Item, which ends up being a double reference (&&T), then you have to either do (|&&n| n < 0) like @blyat did, or (the much uglier imo) (|n| **n < 0) or (|n| n < &&0), so the types match. You can mitigate this by doing .iter().copied() (or .cloned()) to remove the references from .iter(). I'd like to see a .filter() that takes Clone types by value, but I don't think that's allowed in the type system. and it could be a footgun if someone decides to make their 16kiB struct copy. (An example of a real 16kiB struct is the Asahi Linux M1 GPU driver structs, they literally overflow the kernel stack if you try to construct them normally)

Perhaps, but then Swift should be near Rust performance, since it also uses llvm.

@@adaskalov No, because despite Swift also using LLVM the language still does other abstractions e.g. the ABI boxes

Plus for loop is always faster than foreach. So PHP would run faster with a for loop. But it is already very fast thank to C interpreter

What about time spent on I/O? I'm not familiar with Leetcode, but assume that input is read from files, as usual. I suspect that the author of this video used for C++ solutions, which is notorious for being very slow by default.

On leetcode, your don't have to do i/o yourself, as the environment calls your function with all the test cases for you. The author of the video only had to include and

Conor made a video explaining how he makes these transitions, it's pretty cool: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Vh3y1ela-_s.html

My only complaint is the framerate. It's otherwise a really clear and beautiful explanation.

Looks like it's all done by a library called Manim.

You can replicate the C++ std::equal_range manually in C for the best time complexity. Instead of looping to count the number of negatives, you can binary search for the first element that is positive, then count down to the first element that is negative.

@@qqii counting down makes this worst case O(n) 😉

Your right! I translated the "count the number of zeros" from your solution, which is actually O(n) if it's all 0s. That makes the 1 binary search method O(log2(N) + N) So actually ideally you'd do two binary searches, the 2nd with the smaller range (essentially std::lower_bound and std::upper_bound) for O(2 * log2(N)) = O(log2(N)).

@@qqii Better would be to binary search for the 1st non negative, and then, starting by that position, search the first non zero.

@h0rst That solution could still be a bit too slow, imagine the array being passed is made up of 3 negative numbers, 1000 0's and 2 positives, it'll still take awhile to go over the array. Instead peek at the values from both ends at once, say using index starting at 0, while barrier is size_of(array)-1, each pass you increment index and decrement barrier.. once index == barrier *or* (num[index] == 0) && (num[barrier] == 0) .. in this scenario you quit the loop after 3 peeks, for the array example I mentioned.

Kotlin looked too good and readable

why in the world would they chose “it” of all things

it is because it is :)

Yes, the function would end up as ``` fun maximumCount(nums: IntArray): Int { return maxOf( nums.count { it < 0 }, nums.count { it > 0 }, ) } ``` I just found out that youtube doesn't have a way to enter monospace text.

@@vardhanpatil5222 Yep. Unicode has monospace version of the characters of the Latin alphabet and Arabic numerals ( although many fonts render them as something weird ), but not the rest of ASCII.

@code_report Could you give me your insights on the trade off between: 1. Finding/Training developers to read/understand/maintain APL/BQN code vs FP vs imperative programming languages 2. Maintainability/Extensibility of the code base I have the feeling that BQNish code is awesome to certain extent but how can I sell this to my tech lead??

As the others already noticed, the binary search C++ solution has O(N) time complexity because the vector is passed not by reference but by value. Creating a copy of the vector ruins performance.

@@SiarheiSiamashka that's why C++ with const correctness should be the fastest, or same to Rust

Nope. The caller can put nums by rvalue: maximumCount(std::move(nums))

@@kolyan199816 "Can" doesn't guarantee "does". But even without that, I suspect the C++ solution would still be slow. This is a list of 2000 ints. 2k elements of 4 bytes. 8kb. Easily fits inside a l1 cache. The predictability of going linearly through the array is going to outperform the random access required to do a binary search on the array (which is what equal range does under the hood) This is why its important to know your data and your hardware to pick correct algorithms. Ofcourse the only way to know for sure is to measure both and see.

@@khatdubell I feel like they butchered the c++ solutions. There's no need to try to use every single stl function for a single problem. The simpler your code is, like in the c solution, the better it can be optimized.

yes, and that's why it's slower seventy five times than C.

@@xslvrxslwt Yes, python is slower. But it's slower for other reasons, not because of the stylish preference of the commenter.

xslvrxslwt The style is not the issue, for example the haskell version provided can be written maximumCount = (on max length . filter (>0)) (filter (

personally i'd prefer keeping the iterators shorter, to save work on the sum, like this: def maximumCount(self, nums: List[int]) -> int: return max(sum(1 for x in nums if x < 0), sum(1 for x in nums if x > 0)) slight difference in preference, but adding up a list of zeroes at the end is something i don't like. not that the performance difference is likely to be noticable

@@aragonnetje your solution is equivalent to the other one, because the booleans will just be implicitly converted to integer when applying the sum function.

When I started I thought groupMapReduce would do this more elegantly, but really it's more cryptic nums.groupMapReduce(_.sign)(_ => 1)(_ + _).values.max The docs say groupMapReduce is more efficient. I didn't know about _.sign. Thanks for that.

@@Jebusankel looks a bit better with a K combinator: nums.groupMapReduce(_.sign)(const(1))(_ + _).values.max

@@Jebusankel but yeah, it's slightly less clear in what it's doing, especially because gmr isn't really common either

That .clone() was so annoying to watch haha

Wouldnt this increase the space complexity tho brother?

I've got good news and bad news. The good news is that I've made a multithreaded version! The bad news is that it's terrible. (and I'm not sure if I'll be able to give a link)

The PB link id is XtSyyU53

Actually I was able to make a much better version using rayon (PB id 73k7yP4X)

How to code it bdw

@@gshan994 Programming in the comment box will probably be buggy. :.(

The loop will look like this while (len >= 8) { _m256i curr = __mm256_lddqu_si256(*inp256++); _m256i posmask = _mm256_cmpgt_epi32(curr, zero256); _m256i negmask = _mm256_cmplt_epi32(*curr, zero256); posacc = _mm256_sub_epi32(posacc, posmask); negacc = _mm256_sub_epi32(negacc, negmask); len -= 8; } So one load from memory, two compares to generate the masks and two subs to update the accumulators!

@@TerjeMathisen looks cool 😎

Impressive, very nice

Clang has consistently been slower than GCC for me and leetcode timings are a joke

Oh, that's a sweet last solution!

Or, if you prefer the O(log n) way: function maximum_count(nums) zeros = searchsorted(nums, 0) negatives = firstindex(nums) : zeros.start - 1 positives = zeros.stop + 1 : lastindex(nums) maximum(length, (negatives, positives)) end

compilers already those obvious branchless optimisations by default, or use conditional operations (cmov, etc), readability > blind optimization

@@bigboysteen7638 Readability can be improved by comment section

Right, but I think the main improvement in your solution is to use `on` as infix, that just read much more naturally! ;-)

@@chaddaifouche536 Although it's elegant and probably doesn't make a difference for smaller and unsorted inputs, just like std::equal_range I find it quite elegant to actually use the sorted property of the list.

Yeah, I found the majority of these (except Rust, C#, and Kotlin) to be incredibly confusing. Whereas the C solution is simple, clear, and neck-and-neck with Rust.

This is probably what i love the most about C: because the std is bare one you don't waste time using reduction lambda and whatnot. By design the language will make you implement the simplest and (most of the time) fastest solution. A of that while style being clear and readable (not like APL...). Only gripe about the syntax is function pointers, they look atrocious and need you to take a piece of paper to really understand what it actually mean. Would be simpler with a arrow notation.

julia> func(arr::Vector{ 0), sum(arr .< 0)) 10 μs with a 2000 element array amazing stuff

I'm mostly fascinated at it's ability to learn on the spot.

Please show us what APL code ChatGPT came up with at each step.

It seems (to me) like the entire point of the video is to be as clever as possible. It's essentially a showcase of the crazy things these languages can do once you get into the deeper stuff. I don't believe that the narrator would actually advocate for doing this in production code. Code golf is in a similar vein.

Most of the examples in the video seem idiomatic and straightforward to me, especially for the languages that support functional style. I think you just think they're clever because you're not used to them. A for loop will seem like the solution to everything if you only use a language that forces you to use them

Some of the languages don't even have for loops my guy

Yeah I don’t get this insistance on using the most obscure implementation possible. We are programming, not writing math. So use the commands of the programming language.

What's the performance implications of this composed Foldl compared to the hand-written one below? There must be some difference. uncurry max $ foldl' (\acc x -> bimap (+ fromEnum (x > 0)) (+ fromEnum (x < 0)) acc) (0, 0) [-1,-2,-3, 0, 0, 1,2]

@@flowname there’s definitely some overhead to the extra data types needed by , unless the compiler is smart enough to completely remove them. That would be faster but the code is less reusable

@@Axman6 is it always guaranteed to be a single pass at all times though? Extra allocations are fine as long as it always converts to exactly one pass. I guess it's implied by the package when it mentions streaming in the README, but just in case :)

@@flowname yep, the foldl package defines a type which basically matches the arguments you’d give to the foldl function, and takes care of passing each input to each sub-Fold, and aggregating their intermediate states, and also adding a projection function to get the final answer: data Fold a b = forall s. Fold (s -> a -> s) s (s -> b) (Fold function, initial/current state, projection to final type).

A faster Python solution would be: max(sum(x < 0 for x in nums), sum(x > 0 for x in nums))

@@BrianWoodruff-Jr An even faster Python solution would be max(len([x for x in nums if x < 0]), len([x for x in nums if x > 0]))

@@BrianWoodruff-Jr your solution works significantly slower than the one in the video on my machine.

@@ChimeraGilbert Interesting. I tried RoieTBD's solution and it was slower on my machine. You are saying my solution is slower on yours. I wonder how much of that is due to what we set "nums" to, how much to which python version we're using (CPython, pypy, etc), and how much to our hardware.

Another option in Python is to use Numpy. In my experience, that can be several orders of magnitude faster than list comprehension. Eg on a list with 10 million items I worked on recently, execution time went down from 10 minutes to less than a second, not including io time to get the list into memory.

most meaningful comment, yet, no plus.... thanks, i could not have said it better. (Although, the list is already sorted, and there is no need to iterate any further than the first value of '1' found, as long as you know count of negative numbers, the count of zeros, it is just some simple math)

A performant complier should be able to fold and inline these calls

what about some bit operations? given that the numbers are stored in 2s complement, you'd only need to check the first bit for the negative numbers. If you then check how many zeroes there are, you'll know how many numbers are positive by subtracting the current count from the total...

@@genejas My assembly knowledge is quite old but I don't think that a binary bit operation is much faster than a simple number comparison. The number comparison might actually be as fast as the logical bit operation on many processors. If you need the fastest implementation you probably should just implement binary search which special handling of zeroes in a decent language by yourself.

@@HannesSchmiderer fair point, i just assumed they were faster everywhere because they're faster on my most used platform

to prevent some counting up of zeroes in the binary mask, you could also do: max(sum(1 for x in nums if x < 0), sum(1 for x in nums if x > 0))

@@aragonnetje it still scans twice, and if nums is a stream itself, you'll have to tee it with all the implications of tee

the rust solution also uses clone though, since the value isn’t borrowed. So this would make the rust solution even faster right?

@@kasdejong6425 The rust compiler is exceedingly competent at optimizing code. I say this as someone who is not a fan of the language.

Yes, in JS you could write this: Math.max(...nums.reduce(([pos, neg], n) => [pos + (n > 0), neg + (n < 0)], [0,0])) And it would iterate only once

Here's one in BQN: (⌈´ 0⊸≍∘≠ |∘- ⍋⟜¯1‿0) For an array sorted in ascending order, find the last places that -1 and 0 would fit. Take the absolute difference from 0 and length of the array respectively, then maximum.

What made you laugh?

I actually coded Julia as the 25th language but decided 24 (4*6 grid) looked better. 😂 I can came up with: max(sum(xs .< 0), sum(xs .> 0))

For the O(log(n)) solution, you would get something not as pretty: function f(x::Vector{Int64})::Int64 s = searchsorted(x, 0) return max(s.start - 1, length(s) - s.stop) end Would be nice to see a solution that's not prone to an off by one error.

I tested that against my naive approach of count(xs .< 0), and there were 0 allocations and it took 0.3x as long, so that's a good spot!

Hey, as you become more experienced you'll understand the tradeoff between code complexity and performance. Your code would work, but it would be much more complex while only increasing performance by about 0.5. Usually you want to keep the code simple so that others can follow it easily. If speed is very important there are much better algorithms like the binary search or equal_range mentioned in the video.

(0

Gold comment, I didn't know of bisect

It sounds like only C++ and Python can have O(log(n)) solution, as if other languages weren't turning-complete. You can implement your own binary search function as long as you have indices and comparator. I actually don't get why only C++ used logarithmic solution...

But what if there aren't any zeros at all

@@aintaintaword666 You're right. We'd need to adapt binary search to find the position of the first of the positive number and the position of the last negative number from the vector. I typed a solution for the C variant: #include // The vector and the count of elements int *v, n; // Finds the position of the first positive from a given interval in v // Rerurns n if there is no positive number int binary_search_furst_pos(l, r) { // Non-existent interval if (l > r) return n; // One value interval if (l == r) if (v[l] > 0) return l; else return n; int m = (l + r) / 2; // If there is a positive on position m, then keep looking to the left for the first one if (v[m] > 0) { int aux = binary_search_first_pos(l, m - 1); // If there is no positive to the left, then return the one we found if (aux == n) return m; } // If there is a non-positive integer on position m, then we keep looking to the right else return binary_search_first_pos(m + 1, r); } // Finds the position of the last negative from a given interval in v // Rerurns -1 if there is no negative number int binary_search_last_neg(l, r) { // Non-existent interval if (l > r) return -1; // One value interval if (l == r) if (v[l] < 0) return l; else return -1; int m = (l + r) / 2; // If there is a negative on position m, then keep looking to the right for the last one if (v[m] < 0) { int aux = binary_search_last_neg(m + 1, r); // If there is no negative to the right, then return m if (aux == -1) return m; } // If there is a non-negative integer on position m, then we keep looking to the left else return binary_search_last_neg(l, m - 1); } int main() { { // initialize or read n and v // branches are not required ... } int last_neg = binary_search_last_neg(0, n - 1); int first_pos = binary_search_first_pos(0, n - 1); // Store the counts of negatives and positives int cnt_neg = last_neg + 1; int cnt_pos = n - first_pos; // Get the maximum of the 2 counts int max; if (cnt_pos < cnt_neg) max = cnt_neg; else max = cnt_pos; // Print the maxinum to the console printf("%d ", max); }

The correct binary search solution is to branch out when finding a 0 to search for both lower and upper bound of the span of 0s, keeping the closest bounds known to be outside rather than restarting from either end. This is what C++ std::equal_range does.

Here you go: QBASIC version... ------------------------ DEFINT A-Z REDIM A(1 TO 6) LET A(1) = -2: A(2) = -1: A(3) = -1: A(4) = 1: A(5) = 2: A(6) = 3 PRINT maxCount(A()) REDIM A(1 TO 7) LET A(1) = -3: A(2) = -2: A(3) = -1: A(4) = 0: A(5) = 0: A(6) = 1: A(7) = 2 PRINT maxCount(A()) REDIM A(1 TO 4) LET A(1) = 5: A(2) = 20: A(3) = 66: A(4) = 1314 PRINT maxCount(A()) END DEFINT A-Z FUNCTION maxCount (aVector()) DIM dCount(-1 TO 1) FOR J = LBOUND(aVector, 1) TO UBOUND(aVector, 1) LET S = SGN(aVector(J)) LET dCount(S) = dCount(S) + 1 NEXT LET maxCount = dCount(2 * ABS(dCount(-1) < dCount(1)) - 1) END FUNCTION ------------------------ I'll leave the benchmarking and video up to you. 😉

​@@DerekRoss1958 Haha, thanks!!! Now you have to record your voice commenting the code for our video! And we also need people to do the same in Cobol, Algol, Fortran, B and etc... :3 Let me guess, you are 40+ and had a Commodore or ZX Spec when kid?

@@sophiacristina I wish! More like 60+ and I had kids who had a ZX Spec! My first language was actually FORTRAN IV on coding forms. And I have no idea what brand of computer my programs were run on. I sent off the coding forms and got the results back on green-and-white striped paper!

@@DerekRoss1958 That is pretty cool. :) I watch videos about old systems and i saw some stuffs around about FORTRAN, but i never messed up with it myself. Pretty interesting to know things were done this way back then. I never though about a programmer far from the computer. 😮 If there was an error or bug in your code, would you have to discover it only later? That looks cool, i hope one day i can touch older computer and see my modern days programming knowledge working on such systems and printing in paper, haha, i really enjoy this theme... :) I think i'm newer than your kids. I used to mess with computer in the mid 90's when i was kid. Using MS-DOS and Win95. I think if i had a ZX i would have at had more inspiration in programming at an early age. But MS-DOS also made me not lay about computer when i grew up. When i was nearly teen, i had heard about Pascal, C and C++, and one uncle i had used to program on C++.