The behaviour of a system is determined by its Hamiltonian. In many cases, the exact Hamiltonian is not known and has to be extracted by analysing the outcome of measurements. We study the problem of learning a local Hamiltonian Hto a given precision, supposing either we are given copies of its Gibbs state ρ= e−βH/Tr(e−βH) at a known inverse temperature βor we have access to unitary real-time evolution e−itHfor a known evolution time t. Improving on recent results, we show how to learn the coefficients of a local Hamiltonian Hto error εwith S= O(logN/(βε)2) Gibbs states or with Q= O(logN/(tε)2) runs of the real-time evolution, where Nis the number of qubits in the system and if β< βcand t< tcfor some critical inverse temperature βcand critical evolution time tc. We design a classical post-processing algorithm with time complexity linear in the sample size in both cases, namely, O(NS) and O(NQ). In the Gibbs-state input case, we prove a matching lower bound, showing that our algorithm’s sample complexity is optimal, and hence, our time complexity is also optimal.