| | | 1 | | // -------------------------------------------------------------------------------- |
| | | 2 | | // Copyright (C) 2025 Eugene Eremeev (also known as Yevhenii Yeriemeieiv). |
| | | 3 | | // All Rights Reserved. |
| | | 4 | | // -------------------------------------------------------------------------------- |
| | | 5 | | // This software is the confidential and proprietary information of Eugene Eremeev |
| | | 6 | | // (also known as Yevhenii Yeriemeieiv) ("Confidential Information"). You shall not |
| | | 7 | | // disclose such Confidential Information and shall use it only in accordance with |
| | | 8 | | // the terms of the license agreement you entered into with Eugene Eremeev (also |
| | | 9 | | // known as Yevhenii Yeriemeieiv). |
| | | 10 | | // -------------------------------------------------------------------------------- |
| | | 11 | | |
| | | 12 | | namespace LeetCode.Algorithms.CouponCodeValidator; |
| | | 13 | | |
| | | 14 | | /// <inheritdoc /> |
| | | 15 | | public class CouponCodeValidatorBucketSort : ICouponCodeValidator |
| | | 16 | | { |
| | 1 | 17 | | private static readonly Dictionary<string, int> CategoryIndex = new() |
| | 1 | 18 | | { |
| | 1 | 19 | | ["electronics"] = 0, |
| | 1 | 20 | | ["grocery"] = 1, |
| | 1 | 21 | | ["pharmacy"] = 2, |
| | 1 | 22 | | ["restaurant"] = 3 |
| | 1 | 23 | | }; |
| | | 24 | | |
| | | 25 | | /// <summary> |
| | | 26 | | /// Time complexity - O(L + n log n), where L is the total characters in all codes |
| | | 27 | | /// Space complexity - O(n) |
| | | 28 | | /// </summary> |
| | | 29 | | /// <param name="code"></param> |
| | | 30 | | /// <param name="businessLine"></param> |
| | | 31 | | /// <param name="isActive"></param> |
| | | 32 | | /// <returns></returns> |
| | | 33 | | public IList<string> ValidateCoupons(string[] code, string[] businessLine, bool[] isActive) |
| | 2 | 34 | | { |
| | 2 | 35 | | var buckets = GetBuckets(); |
| | | 36 | | |
| | 18 | 37 | | for (var i = 0; i < code.Length; i++) |
| | 7 | 38 | | { |
| | 7 | 39 | | if (!IsCouponValid(code[i], businessLine[i], isActive[i], out var category)) |
| | 4 | 40 | | { |
| | 4 | 41 | | continue; |
| | | 42 | | } |
| | | 43 | | |
| | 3 | 44 | | buckets[category].Add(code[i]); |
| | 3 | 45 | | } |
| | | 46 | | |
| | 2 | 47 | | return CollectSortedResults(buckets); |
| | 2 | 48 | | } |
| | | 49 | | |
| | | 50 | | private static List<string>[] GetBuckets() |
| | 2 | 51 | | { |
| | 2 | 52 | | var buckets = new List<string>[4]; |
| | | 53 | | |
| | 20 | 54 | | for (var i = 0; i < 4; i++) |
| | 8 | 55 | | { |
| | 8 | 56 | | buckets[i] = []; |
| | 8 | 57 | | } |
| | | 58 | | |
| | 2 | 59 | | return buckets; |
| | 2 | 60 | | } |
| | | 61 | | |
| | | 62 | | private static bool IsCouponValid(string code, string category, bool isActive, out int categoryIndex) |
| | 7 | 63 | | { |
| | 7 | 64 | | categoryIndex = -1; |
| | | 65 | | |
| | 7 | 66 | | if (!isActive) |
| | 1 | 67 | | { |
| | 1 | 68 | | return false; |
| | | 69 | | } |
| | | 70 | | |
| | 6 | 71 | | if (!CategoryIndex.TryGetValue(category, out categoryIndex)) |
| | 1 | 72 | | { |
| | 1 | 73 | | return false; |
| | | 74 | | } |
| | | 75 | | |
| | 37 | 76 | | return !string.IsNullOrEmpty(code) && code.All(c => char.IsLetterOrDigit(c) || c == '_'); |
| | 7 | 77 | | } |
| | | 78 | | |
| | | 79 | | private static List<string> CollectSortedResults(List<string>[] buckets) |
| | 2 | 80 | | { |
| | 2 | 81 | | var result = new List<string>(); |
| | | 82 | | |
| | 20 | 83 | | for (var i = 0; i < 4; i++) |
| | 8 | 84 | | { |
| | 8 | 85 | | var bucket = buckets[i]; |
| | | 86 | | |
| | 8 | 87 | | if (bucket.Count == 0) |
| | 5 | 88 | | { |
| | 5 | 89 | | continue; |
| | | 90 | | } |
| | | 91 | | |
| | 3 | 92 | | bucket.Sort(StringComparer.Ordinal); |
| | 3 | 93 | | result.AddRange(bucket); |
| | 3 | 94 | | } |
| | | 95 | | |
| | 2 | 96 | | return result; |
| | 2 | 97 | | } |
| | | 98 | | } |