Day 7 of #100DaysOfCode

🧠 Problem-Solving Journey

𝗗𝗮𝘆 𝟳: 𝗣𝗿𝗼𝗱𝘂𝗰𝘁 𝗼𝗳 𝗔𝗿𝗿𝗮𝘆 𝗘𝘅𝗰𝗲𝗽𝘁 𝗦𝗲𝗹𝗳

𝗣𝗿𝗼𝗯𝗹𝗲𝗺:

𝐶𝑜𝑚𝑝𝑢𝑡𝑒 𝑎𝑛 𝑎𝑟𝑟𝑎𝑦 𝑤ℎ𝑒𝑟𝑒 𝑒𝑎𝑐ℎ 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑡 𝑜𝑓 𝑎𝑙𝑙 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑖𝑛𝑝𝑢𝑡 𝑎𝑟𝑟𝑎𝑦 𝑒𝑥𝑐𝑒𝑝𝑡 𝑖𝑡𝑠𝑒𝑙𝑓, 𝑤𝑖𝑡ℎ𝑜𝑢𝑡 𝑢𝑠𝑖𝑛𝑔 𝑑𝑖𝑣𝑖𝑠𝑖𝑜𝑛 𝑎𝑛𝑑 𝑖𝑛 𝑂(𝑛) 𝑡𝑖𝑚𝑒 𝑐𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡𝑦.

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹On Day 6, I struggled with solving this problem efficiently. I revisited it on Day 7, armed with hints that guided me toward the solution:

🔹𝗛𝗶𝗻𝘁 𝟯: Use the prefix and suffix technique. First, iterate from left to right, storing prefix products for each index in a prefix array (excluding the current index's number). Then, iterate from right to left, storing suffix products for each index in a suffix array (also excluding the current index's number).

🔹𝗛𝗶𝗻𝘁 𝟰: Combine prefix and suffix products by iterating through the array and multiplying them at each index to compute the result array.

🔹Initially, I implemented this approach using separate arrays for prefix and suffix products:

🔹While functional, this solution consumed extra space for the prefix and suffix arrays. To optimize, I reused variables instead of creating arrays:

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: O(n)

📌 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆: This problem taught me how to optimize space by reusing variables instead of creating additional arrays.

𝗗𝗮𝘆 𝟴: 𝗟𝗼𝗻𝗴𝗲𝘀𝘁 𝗖𝗼𝗻𝘀𝗲𝗰𝘂𝘁𝗶𝘃𝗲 𝗦𝗲𝗾𝘂𝗲𝗻𝗰𝗲

𝗣𝗿𝗼𝗯𝗹𝗲𝗺:

𝐹𝑖𝑛𝑑 𝑡ℎ𝑒 𝑙𝑒𝑛𝑔𝑡ℎ 𝑜𝑓 𝑡ℎ𝑒 𝑙𝑜𝑛𝑔𝑒𝑠𝑡 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑡𝑖𝑣𝑒 𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑖𝑛 𝑎𝑛 𝑎𝑟𝑟𝑎𝑦 𝑖𝑛 𝑂(𝑛) 𝑡𝑖𝑚𝑒 𝑐𝑜𝑚𝑝𝑙𝑒𝑥𝑖𝑡𝑦.

𝗘𝘅𝗮𝗺𝗽𝗹𝗲:

Input: nums =[2]

Output: 4 (The sequence is [2])

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹My first instinct was to sort the array and count consecutive elements. However, sorting costs O(nlogn), which violates the O(n) requirement.

🔹Next, I considered using an array indexed by values to track consecutive numbers. This approach worked but required handling negative numbers and large values. I planned to find the minimum value in the array to set an offset for negative numbers.

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: O(n), but space usage could be high for large arrays.

🔹To optimize further, I used a set instead of an indexed array. This reduced space complexity while maintaining linear time complexity:

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: O(n)

📌 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆: Using sets improved both time and space efficiency while simplifying implementation.

𝗗𝗮𝘆 𝟵: 𝗩𝗮𝗹𝗶𝗱 𝗣𝗮𝗹𝗶𝗻𝗱𝗿𝗼𝗺𝗲

𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝟭:

𝐶ℎ𝑒𝑐𝑘 𝑖𝑓 𝑎 𝑠𝑡𝑟𝑖𝑛𝑔 𝑖𝑠 𝑎 𝑝𝑎𝑙𝑖𝑛𝑑𝑟𝑜𝑚𝑒 𝑎𝑓𝑡𝑒𝑟 𝑟𝑒𝑚𝑜𝑣𝑖𝑛𝑔 𝑛𝑜𝑛-𝑎𝑙𝑝ℎ𝑎𝑛𝑢𝑚𝑒𝑟𝑖𝑐 𝑐ℎ𝑎𝑟𝑎𝑐𝑡𝑒𝑟𝑠 𝑎𝑛𝑑 𝑖𝑔𝑛𝑜𝑟𝑖𝑛𝑔 𝑐𝑎𝑠𝑒.

𝗘𝘅𝗮𝗺𝗽𝗹𝗲:

Input: "Was it a car or a cat I saw?"

Output: True (Processed string: "wasitacaroracatisaw")

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹I decided to use two pointers to compare characters from both ends of the string.

🔹Key challenges included handling non-alphanumeric characters and ensuring case insensitivity.

🔹I also had to address edge cases like empty strings or strings with only spaces.

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: O(n)

📌 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆: Preprocessing input data efficiently before applying algorithms is crucial.

𝗣𝗿𝗼𝗯𝗹𝗲𝗺 𝟮:

Check if a string containing parentheses ('(', ')', '{', '}', '[', ']') is valid. A valid string satisfies these conditions:

1) Every open bracket has a corresponding close bracket of the same type.

2) Open brackets are closed in the correct order.

3) Every close bracket has a corresponding open bracket.

𝗘𝘅𝗮𝗺𝗽𝗹𝗲:

Input: "([{}])"

Output: True

🔍 𝗖𝗵𝗮𝗶𝗻 𝗼𝗳 𝗧𝗵𝗼𝘂𝗴𝗵𝘁:

🔹I initially solved this problem using multiple if conditions and a stack:

🔹To optimize further, I used a dictionary to map closing brackets to their corresponding opening brackets:

⏱️ 𝗧𝗶𝗺𝗲 𝗖𝗼𝗺𝗽𝗹𝗲𝘅𝗶𝘁𝘆: O(n)

📌 𝗧𝗮𝗸𝗲𝗮𝘄𝗮𝘆: Using dictionaries simplifies mapping between bracket types while improving readability.

#100DaysOfCode #DSA #Python #ProblemSolving #CodingChallenge #TechLearning