aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-29 18:50:02 -0600
committerJack Sangdahl <[email protected]>2025-06-29 18:50:02 -0600
commit15efdf1024a15a3f8016f31063fc0ce286ef5b2b (patch)
tree093ee02e340c168ed40e9e8860c8a4c580dc001d
parent2815a0d9727446bb9f4a1cbd4bed70eb58e97298 (diff)
downloadleetcode-15efdf1024a15a3f8016f31063fc0ce286ef5b2b.tar.gz
leetcode-15efdf1024a15a3f8016f31063fc0ce286ef5b2b.zip
594. longest harmonious subsequence
-rw-r--r--longest_harmonious_subseq.c62
-rw-r--r--longest_harmonious_subseq.py26
2 files changed, 88 insertions, 0 deletions
diff --git a/longest_harmonious_subseq.c b/longest_harmonious_subseq.c
new file mode 100644
index 0000000..1c1e5b4
--- /dev/null
+++ b/longest_harmonious_subseq.c
@@ -0,0 +1,62 @@
+// 594. Longest Harmonious Subsequence
+#include "leetcode.h"
+
+/*
+ * we define a harmonious array as an array where the difference between its
+ * maximum value and its minimum value is exactly 1. given an integer array
+ * 'nums', return the length of the its longest harmonious subsequnce among all
+ * its possible subsequnces.
+ */
+
+struct hash {
+ int num;
+ int cnt;
+ UT_hash_handle hh;
+};
+
+struct hash *mem;
+static int idx;
+
+int *entry(struct hash **set, int n) {
+ struct hash *tmp;
+ HASH_FIND_INT(*set, &n, tmp);
+ if (!tmp) {
+ tmp = &mem[idx++];
+ tmp->num = n;
+ tmp->cnt = 0;
+ HASH_ADD_INT(*set, num, tmp);
+ }
+ return &(tmp->cnt);
+}
+
+bool contains(struct hash **obj, int num) {
+ struct hash *tmp;
+ HASH_FIND_INT(*obj, &num, tmp);
+ return tmp;
+}
+
+int findLHS(int *nums, int numsSize) {
+ struct hash *set = NULL, *p, *tmp, *s;
+ int ans = 0;
+ idx = 0;
+ mem = (struct hash *)calloc(numsSize, sizeof(struct hash));
+ for (int i = 0; i < numsSize; i++)
+ (*entry(&set, nums[i]))++;
+ HASH_ITER(hh, set, s, tmp) {
+ int key = s->num;
+ if (contains(&set, key + 1)) {
+ int sum = *entry(&set, key) + *entry(&set, key + 1);
+ if (sum > ans)
+ ans = sum;
+ }
+ }
+ free(mem);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 3, 2, 2, 5, 2, 3, 7}, n2[] = {1, 2, 3, 4}, n3[] = {1, 1, 1, 1};
+ printf("%d\n", findLHS(n1, ARRAY_SIZE(n1))); // expect: 5
+ printf("%d\n", findLHS(n2, ARRAY_SIZE(n2))); // expect: 2
+ printf("%d\n", findLHS(n3, ARRAY_SIZE(n3))); // expect: 0
+}
diff --git a/longest_harmonious_subseq.py b/longest_harmonious_subseq.py
new file mode 100644
index 0000000..1252090
--- /dev/null
+++ b/longest_harmonious_subseq.py
@@ -0,0 +1,26 @@
+# 594. Longest Harmonious Subsequence
+from collections import Counter
+
+"""
+we define a harmonious array as an array where the difference between its
+maximum value and its minimum value is exactly 1. given an integer array
+'nums', return the length of the its longest harmonious subsequnce among all
+its possible subsequnces.
+"""
+
+
+class Solution(object):
+ def findLHS(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ c = Counter(nums)
+ return max((c[i] + c[i + 1]) * (c[i + 1] != 0) for i in c)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findLHS(nums=[1, 3, 2, 2, 5, 2, 3, 7]))
+ print(obj.findLHS(nums=[1, 2, 3, 4]))
+ print(obj.findLHS(nums=[1, 1, 1, 1]))