Daily Leetcode : Jul 21, 2026 - 3499. Maximize Active Section with Trade I

[00:00:00]Hey, hey everybody. This is Larry. This is day 21 of the legal day challenge.

[00:00:06]Hit the like button, hit the subscribe button, join me on Discord. Let me know what you think about today's prom. Today we have a medium problem. We'll see how it goes. I went to the gym today. I did bench and then I did squats. So, pretty okay day. But, uh, and you know, I only got like about maybe two more weeks of that because after that I'm doing about 40 to 50 miles a week and that is just too much to do both. Um, I'm trying to maybe work in maintenance. Uh, like just a little bit of bench, a little bit of squats, but well, bench I probably could do, but squats I don't know if I could get out. My legs are always so dead after six days of running. But, uh, yeah, that's kind of how it's going.

[00:00:47]It's this is week four of an 18week program. Same thing I've done twice before. So we'll see how it goes. But uh today I'm feel a little bit better. I slept way too much yesterday in a good way. Um more than I expected, but you know, I woke up very refreshed. But we'll see how long that last. Um yeah, let's take a look at today's prom. We have 34.99 maximum or maximize active section with trade one. Given a binary string s of trade N where one uh one is an active zero is an inactive. You perform at most one trade to maximize number of active sessions in in S. In a trade you could convert a contiguous block of one that's surrounded by zeros to all zeros.

[00:01:37]Afterwards, convert to cont box of zeros that's surrounded by ones to all ones.

[00:01:42]Return the maximum number of active sessions in S after making the optimal trade.

[00:01:51]Okay. Um I think there are two ways to think about it. I'm trying to think, right? Or or I mean there a lot of ways to think about it. First, I guess I'll ch double check and just to make sure it's not something dumb. It's tend to fifth. We have to be a little bit smarter. But really, there only two things to do, right?

[00:02:18]So, you want to optimize all um you optimize the number of ones, right? And there two things you can do at most one trade, but you have to do it. Okay?

[00:02:34]treat. Oh, treat us as if there's once in the thing.

[00:02:39]Okay, that's awkward, but fine, maybe.

[00:02:45]Uh, so you can always convert zeros, I guess. Um, I think a couple of strategies, right? I mean, for all purp um because there nothing to do with how do I even say this? There's a lot there's not that much with um because the the first thing that you want to think about with a problem like this is that because n is big you have to try to figure out how to do it in a way that's independent right meaning in this case maybe you have islands where they interact right and this interaction means interaction at a distance because you can change one region and it maybe propagates to other regions and that's kind of what I mean by like maybe maybe locality is a better word I I that dependence what I mean is maybe dependence for like a far away cell because once you do propagation stuff it always is a little bit sketchy uh the other thing is okay maybe there's a greedy right well by the time we do convert I think okay so the greedy part is if we change a contiguous block of zeros um and they're always going to be yeah zeros to ones and they're always going to unless they're already all ones which is not possible. Can this always happen the first block? Cuz let me double check the constraint. Cuz if it's all ones, then you can trade, right?

[00:04:12]Or am I confused?

[00:04:16]Can we take a box of ones that's surrounded by by zeros, right? But there's no zeros. So, okay. Uh first is that of course at most one means that you also do none. So that's your starting point. Um, so this one you always want to greedy because I think that makes sense. That's just a pure delta. But then the question is, would you do this from one to zero?

[00:04:39]Would you The question is, would you minimize it?

[00:04:48]Cuz the idea here or one idea that I might have is that so you have like some 0, right? Something like this maybe. Uh, and maybe I don't know maybe maybe uh just like someone like this as well, right?

[00:05:03]Um, if you choose greedy, you might choose and maybe this doesn't maybe this math doesn't really work make sense, right?

[00:05:12]Where's my computer slow? Actually, maybe it's my Firefox. Actually, my Firefox is going hot for some reason that I don't know or maybe don't understand.

[00:05:25]That's why I always have to reboot my computer once in a while. All right, let's see what happens if I do this.

[00:05:33]Does this crash? Yep. Okay, good enough though.

[00:05:37]Maybe. Is this still okay? Anyway, my point is that you have something like this. If you do greedy, you convert all these ones to zeros. Um, right. And but and then afterwards, you convert all these zeros to ones, right?

[00:05:53]So that's one way. Of course, in this case, this would be better because if you convert this one one to a zero and then you convert these, it may be bigger, right? And of course, in a greedy kind of way, you can go both ways. You just increase um right?

[00:06:20]Like this could be really big. So that makes you want to choose this. But then you could just find another kind of example such that um you know you go either way or this is really big so you might choose this but this is still the right answer right because that's eight net positive zeros. Um h I think how do I want to think about this? Maybe there's a dumber way more naive way to think about it but but I'm like trying to think right. Um the first thing is that of course so if you convert a of one to zero what does that mean right that means by definition you're by definition um you're connecting two blocks right I mean it doesn't have to be the reason why but you're definitely at least connecting two blocks and so another way of thinking about it is that okay we have two blocks of zeros connected by some ones um they the you know that could be your math right? Uh the delta is just uh these zeros and then add it to your thing. So you could so you can add two groups of adjacent zeros if you want to think about it. Is that the only way to think about it? Can you I think so, right?

[00:07:39]Only because if you kind of Yeah, cuz I think the counter case might be that is there a thing where you know you have something a zero so big and then maybe a one here, right? I in this case, no it doesn't. I mean, even if this is zero, you would still like I'm trying to think of a case where you would throw away the first move to like a distant one, right? Like in this case, obviously, it's not the case, but which is why we're trying to find the counter case. But you could kind of see that if you like maybe it makes sense to kind of just convert these tail ones and then this one just forward away and so then you just kind of do this.

[00:08:26]But of course in in the same case and and you could guess it right you would just convert all these to zeros and then it would you do this plus this which is always greater than throwing it away. So that means that now this problem reduces to um the two the biggest two adjacent group of zeros as the delta ad right I think that's it maybe I'm wrong honestly uh these kind of proves and stuff it's a little bit sketchy and I don't even know but Um, yeah. Yeah. Okay. Uh, maybe I'll just do a goodbye because I'm lazy, right? Um, so you have 4GT and Right. So maybe we just have like a lazy like maybe when you call a stack pass, right? So group is equal to zero then pass.append append length of t or length of list of t because it's a generator you have to convert to a list right so then that now pass will contain all the groups of zeros and then maybe you do something like um yeah for I don't know a b and zip pass I I think there's a cleaner way to write this but that's how I've been writing it okay so also we have to start with um best is equal to zero once is equal to um the initial count and then Maybe like best is equal to max best um 1 + a + b and then return best right I think technically this would be the case right uh because the the thing with a and b is that these are deltas right that's the thing um and once is the initial thing and that's how I set it up all right yolo submit not going to lie I was going to say I'm not going to lie I wouldn't be surprised if this is wrong just because it just feels so wonky the proofs are kind kind of wonky on this one, but um I don't know.

[00:10:56]Um okay, I think that's it. Right. This is linear time. Uh, and the way that I did is kind of linear space because we did it this way. But you could do it like um whatchamacall like progressively, right?

[00:11:10]So I think that would be constant space, right? Because you only have to just keep track of the last zero and that's it. And you don't even care about the ones really at all, right? Um because you're only swapping them just so that you can swap them back out. So you could just even remove the count of num number of ones. I mean obviously you have to count it initially but kind of initially but yeah very interesting problem very easy to get wrong I'm curious what I did before I mean I did make a mistake before but I did the same idea though um I didn't throw away the oh I do do some like weird things with Oh so this is okay so last time I did do the I did handle the case which apparently we don't need to because of the proof that we did Um that's kind of cool. But then we we still use because basically what I did is that I go okay the min group of ones right so then we take the max group of zero we subtract the min group of ones.

[00:12:10]So that's the thing that I said that is not possible I even showed it right so this thing uh where I was like okay um I would subtract this and add this but as I proved um you would just kind of group it on. I don't know if I had visualization back then during that one.

[00:12:25]So maybe that's why I don't know. I mean if during a contest it cost you like maybe a minute to write this and it's usually not wrong unless you wrote it incorrectly because it just gets dominated. So it's not bad bad but obviously it's a little suboptimal last time. Today we did a little bit cleaner.

[00:12:43]Same idea though. Same basic idea. Um and that's it. That's all I have for this one. Let me know what you think.

[00:12:50]Thanks for watching. Stay good. Stay healthy to good mental health. I'll see you later and take care.