I have a non traditional background (non comp sci) and while I understand complexity I wouldn’t have immediately arrived at the solution like this. I think tha

I have a non traditional background (non comp sci) and while I understand complexity I wouldn’t have immediately arrived at the solution like this. I think that rather, I would have done well because I know after doing hundreds of these both as the interviewer and the interviewee that using some sort of Map along with some vague rumblings of “space/time complexity tradeoff” is very often the solution for these types of questions. So I would have immediately gone there first by instinct.