How to encode an array of categories to feed into sklearn
If the sequence of watches is meaningful, then you do need some kind of classifier that creates user/item embeddings from the sequence of watches, so you're probably looking at GRUs and LSTMs. Neural nets aren't overkill here per se. This is a pretty good treatment of the topic: https://towardsdatascience.com/introduction-to-recommender-system-part-2-adoption-of-neural-network-831972c4cbf7

However this simple approach above does mean you have a multi-label class with a lot of dimensions. This can be hard to scale and may not train well without much data. Feature hashing doesn't help so much in the output because you need to map each back to the right video

If you're willing to forego the sequence, which often doesn't carry that much information beyond simple recency (recent watches are more important). Yes the usual way of dealing with this is as a huge matrix factorization problem. Sparse SVD is possible but maybe overkill; ALS is simpler and about as effective, and works well for implicit input like you have here. You can readily add weights to watches with ALS, which can be used to deemphasize older watches.